Question

Given a set of distinct integers, nums, return all possible subsets (the power set).（不同的整數(shù)，返回所有可能的子集，離散數(shù)學(xué)中叫power set，個數(shù)是2的len(list)的次方）

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

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（廣度優(yōu)先）

2. 首先，數(shù)組要排序，在第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: