leetcode 78. Subsets 、90. Subsets II

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

第一题是输入数组的数值不相同，第二题是输入数组的数值有相同的值，第二题在第一题的基础上需要过滤掉那些相同的数值。

level代表的是需要进行选择的数值的位置。

78. Subsets

错误解法：

class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty())
return result;
vector<int> res;
int level = ;
subsets(nums,result,res,level);
return result;
}
void subsets(vector<int>& nums,vector<vector<int> >& result,vector<int>& res,int level){
result.push_back(res);
for(int i = level;i < nums.size();i++){
res.push_back(nums[i]);
subsets(nums,result,res,level+);
res.pop_back();
}
return;
}
};

如果只看代码本身，不看继续的递归，整个for循环执行完成是同一层的所有节点。

level是同一层初始的开始，对于同一层来说是一个固定值。

正确解法：

时间复杂度2的n次方*n

错误解法：

如果是[1,2,3]这个数组，输出的结果不会包含任何一个含有3的子数组

subset的题目必须将每个搜索的节点存储，这个代码每次是在下一个迭代中(即i+1)将上一次的结果进行存储，所以当level=2时把3存入res时，只有在level = 3时才会将这个搜索存入result。

修改的办法要么是直接删除if判断，要么是在if判断中加入result.push_back(res);

class Solution {
public:
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
if(nums.empty())
return result;
vector<int> res;
int level = ;
subsets(nums,result,res,level);
return result;
}
void subsets(vector<int> nums,vector<vector<int>>& result,vector<int> res,int level){
if(level == nums.size()){
return;
}
result.push_back(res);
for(int i = level;i < nums.size();i++){
res.push_back(nums[i]);
subsets(nums,result,res,i+);
res.pop_back();
}
}
};

90. Subsets II

先用sort排序，是为了利用相同数值紧邻。

在整个过程中，在回溯回来的过程中，才会考虑相同的数值跳过。

从搜索树来看，实际上只在同一层进行相同数值判断，而每一层的节点都是通过回溯得到的。错误的解法是在每一个节点都进行判断。

错误解法：

class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty())
return result;
vector<int> res;
int level;
sort(nums.begin(),nums.end());
subsets(nums,result,res,level);
return result;
}
void subsets(vector<int>& nums,vector<vector<int> >& result,vector<int>& res,int level){
result.push_back(res);
for(int i = level;i < nums.size();i++){
if(i > && nums[i] == nums[i-])
continue;
res.push_back(nums[i]);
subsets(nums,result,res,i+);
res.pop_back();
}
return;
}
};

正确解法：

class Solution {
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<vector<int> > result;
if(nums.empty())
return result;
vector<int> res;
int level = ;
sort(nums.begin(),nums.end());
subsets(nums,result,res,level);
return result;
}
void subsets(vector<int>& nums,vector<vector<int> >& result,vector<int>& res,int level){
result.push_back(res);
for(int i = level;i < nums.size();i++){
res.push_back(nums[i]);
subsets(nums,result,res,i+);
res.pop_back();
while(i < nums.size() - && nums[i+] == nums[i])
i++;
}
return;
}
};