思路:回溯
- 我的解法和官方题解不一样,官方题解更加直观,但是我的解法建立的树更加小
- 官方题解的做法是“二叉树式的组合回溯”,左孩子选,右孩子不选
- 我的解法是“数组的最后一个元素作为叶子节点的组合回溯”方法,使用了for循环
- 脑力里面要有图,两张图的区别要搞清楚
代码:
class Solution {
public:
void backTrack(vector<int>& t, vector<vector<int>>& ans, int cur, vector<int>& nums) {
ans.push_back(t);
if (cur == nums.size()) {
return;
}
for (int i = cur; i < nums.size(); ++i) {
t.push_back(nums[i]);
backTrack(t, ans, i + 1, nums);
t.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<int> t;
vector<vector<int>> ans;
backTrack(t, ans, 0, nums);
return ans;
}
};
思路2:位运算暴搜
- 枚举所有情况,子集问题近似于二进制枚举的本质,逐个枚举,遍历所有子集
枚举所有情况
for (int S = 0; S < (1 << n); ++S) {
从低位开始检查是否选用当前元素
for (int i = 0; i < n; i++) {
if (S & (1 << i)) {
t.push_back(nums[i]);
}
}
代码2
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
int n = nums.size();
for (int S = 0; S < (1 << n); ++S) {
vector<int> t;
for (int i = 0; i < n; i++) {
if (S & (1 << i)) {
t.push_back(nums[i]);
}
}
ans.push_back(t);
}
return ans;
}
};