78.子集

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

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

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

思路

基本想法

使用回溯法，将子集的搜索过程分成横向搜索和纵向搜索

横向搜索每次拿nums中的一个元素x去组成子集、

纵向搜索每次从x开始向后开始求出不同的组合，具体的搜索过程形成了一个树的结构

执行流程

回溯的地方有两处，第一处在从x出发递归到触发结束条件时，第二处在for循环结束时

以上图举例就是得到子集[1,2,3]之后，触发递归返回条件，此时回溯将pop_back(3)，下标为2

回到for循环之内时，发现访问到了元素3（下标为2），是nums的最后一个元素，此时触发for循环退出条件（++i==nums.size()），i本身为2，本层递归结束

回到了[1,2]这一层，执行pop_back(2)，下标为1，继续for循环，不满足for循环退出条件

执行两次回溯之后，子集中的元素变成了[1]，此时横向遍历，取出元素3，形成[1,3]，之后再次触发两次回溯

一次递归扫描到了nums的末尾，一次for循环扫描到了nums的末尾，此时子集中为[null]，横向遍历选择[2]。。。

区别

触发递归返回条件之后，先回到上层再pop_back()，之后进行for循环，可能触发for循环结束条件，此时是本层程序走到末尾返回，回到上层pop_back()之后，继续for循环。。。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    //全局变量存放结果和子集
    vector<vector<int>> res;
    vector<int> path;
    vector<vector<int>> subsets(vector<int>& nums) {
        backtrack(nums,0);
        return res;
    }
    void backtrack(vector<int>& nums,int index){
        res.push_back(path);//进入当前递归就保存一次结果
        if(index==nums.size()){
            return;
        }
        //进入横向搜索
        for(int i=index;i<nums.size();++i){
            //没有重复元素，不需要判断是否遍历到了重复元素
            path.push_back(nums[i]);
            //纵向遍历
            backtrack(nums,i+1);
            //遇到递归结束或者for循环结束返回上层
            path.pop_back();
        }
    }
};

总结

明确代码执行的流程，何时返回，以及搜索形成的集合什么时候加入结果集。