class Solution:
    def subsets_recursive(self, nums):
        """
        O(n*2^n)

        :type nums: List[int]
        :rtype: List[List[int]]

        Given a set of distinct integers, nums, return all possible subsets (the power set).
        Note: The solution set must not contain duplicate subsets.

        Example:

        Input: nums = [1,2,3]
        Output:
        [
          [3],
          [1],
          [2],
          [1,2,3],
          [1,3],
          [2,3],
          [1,2],
          []
        ]

        """
        # [1,2,3], [ [],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3] ]
        res = []
        self.generateSet(nums, 0, res, [])
        return res

    def generateSet(self, nums, startingPos, res, subRes):
        res.append(subRes[:])
        for i in range(startingPos, len(nums)):
            subRes.append(nums[i])
            self.generateSet(nums, i + 1, res, subRes)
            subRes.pop()