这是一道求子集的题目,题目链接,一开始用了三重循环,复杂度极高,不过还是没有超时。代码如下
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
set<set<int>> ans_s;
ans_s.insert(set<int>({}));
for(int i = 0; i <= nums.size(); i++){
auto tmp = ans_s;
for(auto num : nums){
for(auto s_s : tmp){
s_s.insert(num);
ans_s.insert(s_s);
}
}
}
vector<vector<int>> ans;
for(auto s : ans_s){
ans.push_back(vector<int>(s.begin(), s.end()));
}
return ans;
}
};
代码思路就是每次加入一个数字,得到当前的所有子集。直到所有数字都被加入。这中做法使用set来去除重复。
第二种的思路是用回溯的思想,参考了前一道题目的代码。代码如下
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> ans;
helper(nums, 0, vector<int>(), ans);
return ans;
}
void helper(vector<int> &nums, int pos, vector<int> out, vector<vector<int>> &ans) {
ans.push_back(out);
for(int i = pos; i < nums.size(); ++i) {
out.push_back(nums[i]);
helper(nums, i+1, out, ans);
out.pop_back();
}
}
};
网友评论