1. 题意

给定一个不含有重复数字的数列，求所有的子集。

2. 题解

子集型回溯，可以直接用dfs进行搜索；也可以用二进制来进行枚举。

2.1 选或不选

class Solution {
public:void dfs(vector<vector<int>> &ans,vector<int> &tmp,vector<int> &nums, int depth) {if (depth == nums.size()) {ans.emplace_back(tmp );return;}dfs(ans, tmp, nums, depth + 1);tmp.push_back(nums[depth]);dfs(ans, tmp, nums, depth + 1);tmp.pop_back();}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;dfs( ans, tmp, nums, 0);return ans;}
};

2.2 选哪个

class Solution {
public:void dfs(vector<vector<int>> &ans,vector<int> &tmp,vector<int> &nums, int depth) {ans.emplace_back(tmp);for (int i = depth;i < nums.size(); i++) {tmp.push_back(nums[i]);dfs(ans, tmp, nums, i + 1);tmp.pop_back();}}vector<vector<int>> subsets(vector<int>& nums) {vector<vector<int>> ans;vector<int> tmp;dfs( ans, tmp, nums, 0);return ans;}
};

2.3 二进制枚举

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

参考

0x3f题解