78. 子集

应该是一个很经典的递归问题
这位大佬写的很好（题解的搬运工）：
三种方法求解子集

1、考虑层序遍历求解，每次加入一个元素就扩充res的长度，直到所有元素添加完毕。

方便理解，我画成了子集树的形式，相当于每次迭代都向右下↘顺延后，加一个元素生成左边<=的结点，因此每一次迭代都会使res内vector数量double

#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <vector>
using namespace std;

class Solution {
  public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> res(1);
        for (int i = 0; i < nums.size(); i++) {
            int len = res.size();
            for (int j = 0; j < len; j++) {
                vector<int> tmp = res[j];
                tmp.push_back(nums[i]);
                res.push_back(tmp);
            }
        }
        return res;
    }
};

int main() {
    Solution s;
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> res;
    res = s.subsets(nums);
    for (int i = 0; i < res.size(); i++) {
        for (int j = 0; j < res[i].size(); j++) {
            cout << res[i][j] << " ";
        }
        cout << endl;
    }

    cout << endl << res.size();

    return 0;
}

2、回溯求解

class Solution {
  public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> res;
        vector<int> item;
        helper(res, item, nums, 0);
        return res;
    }

    void helper(vector<vector<int>> &res, vector<int> item, vector<int> &nums,
                int level) {
        if (item.size() <= nums.size())//其实这一行注释掉也可以，下面i<nums.size()已经保证了item.size()不会超过nums.size()
            res.push_back(item);
        for (int i = level; i < nums.size(); i++) {
            item.push_back(nums[i]);
            helper(res, item, nums, i + 1);
            item.pop_back();
        }
    }
};

3、深度优先遍历求解

class Solution {
  public:
    void helper(vector<vector<int>> &res, vector<int> tmp, vector<int> &nums,
                int level) {
        if (level >= nums.size()) {
            res.push_back(tmp);
            return;
        }
        tmp.push_back(nums[level]);
        helper(res, tmp, nums, level + 1);
        tmp.pop_back();
        helper(res, tmp, nums, level + 1);
    }

    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> res;
        vector<int> tmp;
        helper(res, tmp, nums, 0);
        return res;
    }
};

4、位运算
出处

class Solution {
  public:
    vector<vector<int>> subsets(vector<int> &nums) {
        vector<vector<int>> res;
        int size = nums.size();
        for (int i = 0; i < (1 << size); i++) {
            vector<int> tmp;
            for (int j = 0; j < size; j++) {
            // 根据[i] 的二进制数中 [1] 的位置取得子集
                if ((i & (1 << j)) != 0) {
                    tmp.push_back(nums[j]);
                }
            }
            res.push_back(tmp);
        }
        return res;
    }
};