Question

Given a set of distinct integers, nums, return all possible subsets (the power set).（不同的整数，返回所有可能的子集，离散数学中叫power set，个数是2的len(list)的次方）

Note: The solution set must not contain duplicate subsets.(不重复的子集)

Example:

#2的三次方8个子集
Input: nums = [1,2,3]
Output:
[
  [3],
  [1],
  [2],
  [1,2,3],
  [1,3],
  [2,3],
  [1,2],
  []
]

Thought(思路)

1. Backtracking(the red arrows 红色箭头就是backtracking), DFS（广度优先）

2. 首先，数组要排序，在第n层，加入一个元素进入n+1层，删除刚刚加入的元素，加入第n层的第二个元素......

   
   
   thought

Code

class Solution:
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        self.res = []
        def dfs(nums,temp,i):
            self.res.append(temp[:])
            for i in range(i,len(nums)):
                temp.append(nums[i])
                dfs(nums,temp,i+1)
                temp.pop()
                
        dfs(nums,[],0)
        return self.res

Complexity

Time complexity:
Space complexity: