Intuition
- Start from an empty subset, and ask yourself: For each element in my array, I can either include it into the current sub-array, or not include it. This is similar to House Robber intuitively.
Complexity
Runtime
for choice to include or not include on each index.
Space
since each element in your res array contains at most N elements, and there are N of them.
Code
Bottom Up
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]] # Start with the empty subset
for num in nums:
# For each existing subset, create a new subset by adding the current number
res += [curr + [num] for curr in res]
return resTop Down Without Reliance on Non-local
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
def bt(start, cur_subset):
cur = [cur_subset.copy()]
for i in range(start, len(nums)):
cur_subset.append(nums[i])
cur.extend(bt(i + 1, cur_subset))
cur_subset.pop()
return cur
return bt(0, [])Top Down
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def r(start, cur_subset):
res.append(cur_subset.copy())
for i in range(start, n):
cur_subset.append(nums[i])
r(i + 1, cur_subset)
cur_subset.pop()
r(0, [])
return resRecursive 5% Speed (Top Down)
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def r(arr):
nonlocal res
if arr not in res:
res.append(arr)
for i in range(len(arr)):
arrCopy = arr.copy()
arrCopy.pop()
r(arrCopy)
r(nums)
return resInfo
Requires O(N^2) extra space for each recursive call, and there are extra calls.
Solution that Didn’t Work
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for k in range(len(nums)):
for i in range(k, len(nums)):
curNums = []
for j in range(i, len(nums)):
curNums.append(nums[j])
if curNums not in res:
res.append(curNums.copy())
return res
- Missing [1, 3]