# Subsets

ArrayBacktrackingBit

## # Solution

There are $2^n$ possibilities, and for each possibility $i$ it takes $n$ operations to add/not add the nums[i] element. Hence the time complexity $O(n\cdot 2^n)$.

Complexity

time: $O(n\cdot 2^n)$
space: $O(n\cdot 2^n)$

def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]

for num in nums:
res += [subset + [num] for subset in res]

return res

1
2
3
4
5
6
7

### # Backtracking 1

Complexity

time: $O(n\cdot 2^n)$
space: $O(n)$

def subsets(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res = []
temp = []

def backtrack(i):
if i == n:
# have to copy temp by value
res.append(temp[:])
return
temp.append(nums[i])
backtrack(i+1)
temp.pop()
backtrack(i+1)

backtrack(0)
return res

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

### # Backtracking 2

def subsets(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []

def backtrack(nums, path):
res.append(path[:])
for i in range(len(nums)):
path.append(nums[i])
backtrack(nums[i+1:], path)
path.pop()

backtrack(nums, [])
return res

1
2
3
4
5
6
7
8
9
10
11
12
13

### # Binary Sorted Subsets

Each temp can be represented as a binary string. If a digit i is $1$, nums[i] is in; o.w., it's not.

Complexity

time: $O(n\cdot 2^n)$
space: $O(n)$

def subsets(self, nums: List[int]) -> List[List[int]]:
res = []

n = len(nums)
for mask in range(1 << n):
temp = []
for i in range(n):
if mask & (1 << i):
temp.append(nums[i])
res.append(temp)

return res

1
2
3
4
5
6
7
8
9
10
11
12