我只是喜欢敲代码@_@
给定一个整数数组 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 中的所有元素 互不相同
class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
set<vector<int>>sons;
for(auto & num:nums){
set<vector<int>>temp;
for(auto it:sons){
it.push_back(num);
temp.insert(it);
}
sons.insert(temp.begin(),temp.end());
sons.insert({num});
}
vector<vector<int>>answer;
answer.push_back({});
for(auto & it:sons)
answer.push_back(it);
return answer;
}
};
先说一下解法哈,子集问题有很多种解决方法,我写的这个只有两层循环,回溯递归之类的也能写,这是C++写的代码,有大佬可以用四行python解决,同样的解决思路。
对于一串数字,我们想要找出它的所有子集,像1,2,3这个,我们第一次取出1,它自己本身是一个子集,我们把它存起来,第二次取出2,把2插入之前找到的子集中,就有了1,2这个子集,再把它自己存进去,第三次取出3,把3插入之前找到的子集,这样就会有1,3和2,3和1,2,3这些子集,再把3自己存进去。
基本思路是这样,实际操作的时候,会出现重复的子集,所以我们需要先用set来去重,嘻嘻嘻,你会不会有一个疑惑,为什么不一开始就用set,非要我们返回一个vector的呢,我起初也有这样的疑惑,直到我发现set不会存在{}这个空集,而vector可以装一个{}的时候就豁然开朗了。
还有一个问题,我依照这样的思路写的第一次代码其实长这样:
for(auto num:nums){
for(auto it:sons){
it.push_back(num);
sons.insert(it);
}
sons.insert({num});
}
没有引入一个临时变量temp,直到运行超时,手动调试发现这个地方无限循环,原因在于sons每次都加一个元素,然后就不会终结循环,所以得引入一个变量。