Subsets

Backtracking

Given an integer array nums, return all possible subsets (the power set).

The solution set must not contain duplicate subsets.

For example:

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

Input: nums = [0]
Output: [[],[0]]

We apply backtracking by generating all the possible sets for num[i]. For this problem, backtracking is similar to DFS where we go down the branch, seeing all possible combinations for that num[i]
How do we know when a solution is computed so we don't try to solve that solution again?
- Our for-loop will let us know when we reached the end of a branch we are exploring with the help of our pointer variable.

Solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        soln = []
        self.helper(nums, soln, [], 0)
        return soln
            
    def helper(self, nums, soln, curr, index):
        soln.append(list(curr))
        
        # choosing path to go down.
        for i in range(index, len(nums)):
            curr.append(nums[i])
            self.helper(nums, soln, curr, i+1)
            curr.pop()

Key Points

It's like DFS with exploring paths.
The for-loop is the really important part here. Each unique for-loop helps us decide which "branch" we are going down. The next iteration of a specific for loop "skips" the previous branch since we already saw or computed it and don't need it anymore
For-loop essentially controls which path we are going down
We have to make a copy of the current path list when we append to solution list since in a recusive call, if you append a list to another list it will append the reference to the original list (which is the empty list we passed in originally).

Time Complexity

- 2) We need to create a copy of the current set because we reuse the original one to build all the valid subsets. This copy costs O(n) and it is performed at each call of the recursive function, which is called 2^n times as mentioned in above

PreviousBacktracking Introduction NextSubsets II

Last updated 4 years ago

Was this helpful?

Solution

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        soln = []
        self.helper(nums, soln, [], 0)
        return soln
            
    def helper(self, nums, soln, curr, index):
        soln.append(list(curr))
        
        # choosing path to go down.
        for i in range(index, len(nums)):
            curr.append(nums[i])
            self.helper(nums, soln, curr, i+1)
            curr.pop()

Key Points

It's like DFS with exploring paths.

The for-loop is the really important part here. Each unique for-loop helps us decide which "branch" we are going down. The next iteration of a specific for loop "skips" the previous branch since we already saw or computed it and don't need it anymore

For-loop essentially controls which path we are going down

We have to make a copy of the current path list when we append to solution list since in a recusive call, if you append a list to another list it will append the reference to the original list (which is the empty list we passed in originally).

Time Complexity

Time: $O(n * 2^n)$ because

1) The recursive function is called $2^n$ times. Because we have 2 choices at each iteration in the nums array. Either we include nums[i] in the current set, or we exclude nums[i].
2) We need to create a copy of the current set because we reuse the original one to build all the valid subsets. This copy costs O(n) and it is performed at each call of the recursive function, which is called 2^n times as mentioned in above

Space: $O(n * 2^n)$ because the recursion stack is used $2^n$ times and we have our return solution list which is $n$ space.