78. 子集

问题

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]

分析

受此前全排列问题的启发，解答回溯问题时，可以把模拟的递归path先列出来，再通过观察其变化，确定需要用到的状态变量及其可能的修改。

第一列1表示当前path需要加到res中，即dfs过程；0表示不加，即回溯过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
1 1 
1 1 2 
1 1 2 3 
0 1 2 
0 1 
1 1 3 
0 1 
0 _
1 2 
1 2 3 
0 2
0 _
1 3
  1. 还是以数组的index作为参数传给dfs，递归终止的条件是index大于nums_len；
  2. 每次变化的path都需要加到res中；
  3. 每深一层递归的循环起始位置都应该从上一层递归的index + 1 开始；
  4. path要有一个回溯的状态更新；
  5. 因为此题不包含重复元素，且每次循环不需要从index = 0处开始，因此不需要visited数组；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# python
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        def backtrack(index): # 1
            if index > self.length: return # 1
            res.append(path.copy()) # 2
            for i in range(index, self.length): # 3
                path.append(nums[i])
                backtrack(i + 1)
                path.pop() # 4

        res = []
        path = []
        self.length = len(nums)
        backtrack(0)
        return res 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// java
class Solution {
    List<List<Integer>> res = new ArrayList<List<Integer>>();
    List<Integer> path = new ArrayList<Integer>();
    public List<List<Integer>> subsets(int[] nums) {
        backtrack(0, nums);
        return res;
    }
    private void backtrack(int index, int[] nums){
        if (index > nums.length){return;}
        res.add(new ArrayList<Integer>(path));
        for (int i = index; i < nums.length; ++i){
            path.add(nums[i]);
            backtrack(i + 1, nums);
            path.remove(path.size()-1);
        }
    }
}