78. Subsets

Medium

Problem:

Return all subsets.

Input: nums = [1,2,3]
Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

https://leetcode.com/problems/subsets

Solution:

1. For each number in nums, you have two choices:

   • Include the number in the current subset.

   • Exclude the number from the current subset.

2. Recursively apply the above choices for the remaining numbers.

This approach will generate all possible subsets of nums without any duplicates.

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(index, cur):
            # Append the current subset to the result
            result.append(cur[:])
            print(result)

            # Explore further subsets by including numbers from the current index onwards
            for i in range(index, len(nums)):
                cur.append(nums[i])
                dfs(i + 1, cur)
                cur.pop()

        dfs(0, [])
        return result

Better approach

Tree's All DFS Results: This problem can be approached by constructing a tree and performing a DFS on it.

1. While creating the path, we can perform a deep search by incrementing the index by 1.

2. Since every search path eventually becomes an answer for the subsets, there's no need for a specific termination condition. Every time a search is performed, a result is added immediately.

       [ 1,    2,    3 ]
        / \    |
       2   3   3
      /
     3

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        result = []

        def dfs(index, path):
            result.append(path)

            for i in range(index, len(nums)):
                dfs(i + 1, path + [nums[i]])

        dfs(0, [])
        return result