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(思路)
- Backtracking(the red arrows 红色箭头就是backtracking), DFS（广度优先）
-
首先，数组要排序，在第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:
