leetcode 78 子集问题

Posted on | In

题目描述

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

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

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

特别注意，此题是求解字节，并不是求全排列，要区分跟全排列的区别，所示这个地方在处理起点的时候要特别注意一下，而且，子集合是包含空集的，所以在一定程度上是不需要return的。

主要思路

该题的主要思路还是延续基于DFS的回溯的方法，来进行求解，顾先回顾下。

1
2
3
4
5
6
7
8
9
10
11
backtracking() {
    if (终止条件) {
        进行存放数据或者直接输出（Do sth）;
    }
 # PB[] state（可以进行选择，判断节点是否用到过）
    for (选择：选择列表（树中节点的数量）) {
        递归，处理节点;
        backtracking();
        回溯，恢复现场
    }
}

故按这个套路来求解，所以首先确定递归的终止条件，一般的时候是开始的下标大于等于节点的数目的时候进行终止，但是在该题目中，是取子集，遍历整棵树，不需要进行剪枝，故整个代码是不需要终止条件的，所以上述代码中的

1
if(condition)  # 这一步可以忽略了

下面就是核心代码，也就是递归回溯的那一部门，首先 vector<int> path 来存储每一步回溯子集结果，然后vector<vector<int>> result 来吧子集的结果都存储下来，特别注意，因为子集是无序的，所以所以for循环要从startIndex开始,而不是从0开始，故明确这几点后，开始写for循环以及递归的核心

1
2
3
4
5
for(int i=startIndex;i<num.size();i++){
  path.push_back(num[i]); //将该节点加入到子集中
  backtracking(nums,i+1);//递归进入下一层
  path.pop_back(); // 将该节点弹出，恢复现场
}

然后再写好之后，就每次递归调用的时候，把终止条件的地方改成result.push_back(path) 即可。
所有的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
private:
    vector<vector<int>> result;
    vector<int> path;
    void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path);
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }
public:
    vector<vector<int>> subsets(vector<int>& nums) {
        result.clear(); //清空vector
        path.clear();
        backtracking(nums, 0);
        return result;
    }
};

解答参考：https://leetcode-cn.com/problems/subsets/solution/78-zi-ji-hui-su-sou-suo-fa-jing-dian-ti-mu-xiang-2/