Subsets

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)$.

Cascading

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

Backtracking 1

从输入的角度思考 每个数可以在子集中（选）
也可以不在子集中（不选）
叶子是答案
回溯三问：

• 当前操作：枚举 i 个数选/不选
• 子问题：构造字符串 >= i 的部分
• 下一个子问题：构造字符串 >= i+1 的部分

Complexity

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

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

    def backtrack(i):
        if i == n:
            res.append(path[:])
            return res
        
        # not choose current num
        backtrack(i+1)
        
        # choose current num
        path.append(nums[i])
        backtrack(i+1)
        path.pop()
    
    backtrack(0)
    return res

Backtracking 2

从答案的角度思考
枚举第一个数选谁
枚举第二个数选谁
每个节点都是答案

注意：
[1, 2] 和 [2, 1] 是重复的子集
为了避免重复
下一个数应大于当前选择的数
回溯三问：

• 当前操作：枚举一个下标 j >= i 的数字，加入 path
• 子问题：从下标 >= i 的数字中构造子集
• 下一个子问题：从下标 >= j+1 的数字中构造子集

def subsets(self, nums: List[int]) -> List[List[int]]:
    n = len(nums)
    res = []
    path = []
    
    def backtrack(i):
        res.append(path[:])
        if i == n:
            return res
        
        for j in range(i, n):
            path.append(nums[j])
            backtrack(j+1)
            path.pop()
    
    backtrack(0)
    return res

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