Solutions

# Backtracking. For each number, we can either include it in the current subset or not. We recurse on both possibilities until we reach the end of the list.
# backtracking

# O(2^n) time, O(n) space (2^n subsets, and O(n) space for the recursion stack)
def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    recurse(nums, [], res, 0)
    return res

def recurse(nums: list[int], current: list[int], res: list[list[int]], idx: int):
    if idx == len(nums):
        res.append(current)
        return

    recurse(nums, current + [nums[idx]], res, idx+1)
    recurse(nums, current, res, idx+1)

# Alternative
def subsets(nums: list[int]) -> list[list[int]]:
    res = []
    subset = []

    def dfs(i):
        if i >= len(nums):
            res.append(subset.copy())
            return
        subset.append(nums[i])
        dfs(i + 1)
        subset.pop()
        dfs(i + 1)

    dfs(0)
    return res


# Iterative approach: start with an empty subset, and for each number, add it to all existing subsets to create new subsets.
# O(2^n) time, O(2^n) space
def subsets(nums: list[int]) -> list[list[int]]:
    res = [[]]

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

    return res