子集

问题描述

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

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

示例:

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

来源：LeetCode

解法一

对于子集问题，对每一个元素，我们都有选和不选两种选择，如何模拟这两种选择？可以使用递归回溯，递归参数保存了当前待访问的元素索引，临时子集保存在vector中，递归出口是当前待访问的索引为数组的长度，则保存临时子集的结果。

回溯法是一种递归寻找符合要求的解的方法，适用的问题是决策树类型，即在决策树怎么一步一步遍历。回溯的框架需要考虑三个变量：1.当前已走路径，2.当前可选路径列表，3.结束条件（符合条件或到达决策树底部）。

在下述代码中，have保存当前已走路径，可选路径只有两条，那就是对当前元素，走还是不走。不走，则对应一个回溯函数，回溯到底部，并保存结果；走，则保存当前元素到have中，回溯返回后，对撤销have中已选的当前节点，回到上一个状态（为什么撤销，这里have是引用类型，是为了节省形参内存，不是引用类型，那么撤不撤销都不会影响下一次选择）

时间复杂度：有2n个子集（2n次调用回溯函数），每个子集复制到结果集合，需要O(n)，所以最后时间复杂度为O(n*2^n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> res;
    vector<vector<int>> subsets(vector<int>& nums) {
        vector<int> have;
        helper(nums, have, 0);
        return res;
    }

    void helper(vector<int>& nums, vector<int> & have, int index) { // from 0
        if(index == nums.size()) {
            // 递归出口 保存结果
            res.push_back(have);
            return;
        }
        helper(nums, have, index+1); // 不使用当前元素
        have.push_back(nums[index]); // 使用当前元素
        helper(nums, have, index+1);
        // 当前选择不会对下一次选择产生影响
        have.pop_back(); // 每次have在helper输入输出中是不变的
    }
};