Subsets

2 min read
LC-Medium
Backtracking

Oct 21, 2022

3 years ago

LeetCode

Solution

Backtracking Depth-first Search
At each point, you have two choices: either add the current number to the subset we're building, or not
Basically just that. Just do it until we reach the end of nums
We won't have duplicate subsets formed this way because:
- When generating subsets, you don't need to check if a number is already in the current subset because each subset is built from a unique combination of indices, not values.
- We make two unique choices at each point, and this prevents duplicates from being formed.

Time	Space	Explanation
`O(n * 2^n)`	`O(n * 2^n)`	2^n for the recursive calls- n for copying value of `cur` to `ans`

def subsets(self, nums: List[int]) -> List[List[int]]: cur, ans = [], [] def dfs(i): if i == len(nums): ans.append(cur[:]) return dfs(i + 1) cur.append(nums[i]) dfs(i + 1) cur.pop() dfs(0) return ans

Alternative Soln.

def subsets(self, nums: List[int]) -> List[List[int]]: ans = [] def dfs(i, sub): if i == len(nums): ans.append(sub) return dfs(i + 1, sub + [nums[i]]) dfs(i + 1, sub) dfs(0, []) return ans