给你一个整数数组
nums
,数组中的元素
互不相同 。返回该数组所有可能的子集(幂集)。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1:
输入:nums = [1,2,3]
输出:[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2:
输入:nums = [0]
输出:[[],[0]]
提示:
- 1 <=
nums.length
<= 10 - -10 <=
nums[i]
<= 10 -
nums
中的所有元素互不相同
题解1 回溯
class Solution {
vector<vector<int>> ret;
deque<int> tmp;
public:
void backtrace(vector<int>& nums, int len, int idx){
if(len > nums.size()) return;
if(tmp.size() == len){
ret.push_back(vector<int>(tmp.begin(), tmp.end()));
// idx 此时还没用过
backtrace(nums, len+1, idx);
return;
}
for(int i = idx; i < nums.size(); i++){
tmp.push_back(nums[i]);
backtrace(nums, len, i+1);
tmp.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtrace(nums, 0, 0);
return ret;
}
};
模板
class Solution {
vector<vector<int>> ret;
vector<int> tmp;
public:
void backtrace(vector<int>& nums, int idx){
if(idx == nums.size()){
ret.push_back(tmp);
return;
}
tmp.push_back(nums[idx]);
// 选
backtrace(nums, idx+1);
tmp.pop_back();
// 不选
backtrace(nums, idx+1);
}
vector<vector<int>> subsets(vector<int>& nums) {
backtrace(nums, 0);
return ret;
}
};
文章来源:https://www.toymoban.com/news/detail-722034.html
题解2 迭代(mask思想)
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ret;
vector<int> tmp;
int s = nums.size();
// 每个子集对应一个长度为s的01序列,第i位表示nums[i]是否在子集中
// mask 的值代表tmp当前有多少个元素,以及nums哪几个元素在tmp里
for(int mask = 0; mask < 1 << s; mask ++){
tmp.clear();
for(int i = 0; i < s; i++)
// 根据mask的值把元素放到tmp里
if(mask & (1<<i))
tmp.push_back(nums[i]);
ret.push_back(tmp);
}
return ret;
}
};
文章来源地址https://www.toymoban.com/news/detail-722034.html
到了这里,关于78 子集的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!