def subsets(nums):
    """
    O(2**n)
    """
    def backtrack(res, nums, stack, pos):
        if pos == len(nums):
            res.append(list(stack))
        else:
            # take nums[pos]
            stack.append(nums[pos])
            backtrack(res, nums, stack, pos+1)
            stack.pop()
            # dont take nums[pos]
            backtrack(res, nums, stack, pos+1)

    res = []
    backtrack(res, nums, [], 0)
    return res
O(2**n)