Subsets

ArrayBacktrackingBit
https://leetcode.com/problems/subsets

# Solution

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

# Cascading

Complexity

time: O(n2n)O(n\cdot 2^n)
space: O(n2n)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(n2n)O(n\cdot 2^n)
space: O(n)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 11, nums[i] is in; o.w., it's not.

Complexity

time: O(n2n)O(n\cdot 2^n)
space: O(n)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