LeetCode40：组合总和II——解析与优化算法

这道题是LeetCode里的第40道题。

题目要求&＃xff1a;

给定一个数组 candidates 和一个目标数 target &＃xff0c;找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明&＃xff1a;

所有数字(包括目标数)都是正整数。

解集不能包含重复的组合。

示例 1:

输入: candidates &＃61; [10,1,2,7,6,1,5], target &＃61; 8,

所求解集为:

[

[1, 7],

[1, 2, 5],

[2, 6],

[1, 1, 6]

]

示例 2:

输入: candidates &＃61; [2,5,2,1,2], target &＃61; 5,

所求解集为:

[

[1,2,2],

[5]

]

解法和第39题几乎一样&＃xff0c;区别在于本题每一个数字只能使用一次&＃xff0c;但数字在数组中是可以重复的。同样&＃xff0c;还是使用回溯剪枝法&＃xff0c;先对 candidates数组元素排序。排序后进行循环递归。具体代码如下&＃xff1a;

提交代码&＃xff1a;

class Solution {

public:

vector> res;

vector ans;

void getres(vector& candidates,int target,int k,vector ans){

int size&＃61;candidates.size();

for(int i&＃61;k;i

if(target-candidates[i]>0){

if(i>k&&candidates[i]&＃61;&＃61;candidates[i-1])continue;

ans.push_back(candidates[i]);

getres(candidates,target-candidates[i],i&＃43;1,ans);

ans.pop_back();

}

else if(target-candidates[i]<0){return;}

else{

ans.push_back(candidates[i]);

res.push_back(ans);

ans.pop_back();

return;

}

}

return;

}

vector> combinationSum2(vector& candidates, int target) {

sort(candidates.begin(),candidates.end());

getres(candidates,target,0,ans);

return res;

}

};

代码和第39题几乎一样&＃xff0c;只改了两个地方&＃xff0c;第一个是第11行&＃xff0c;参数由 i 改为 i&＃43;1&＃xff0c;这是能想到的确保每一个数字只使用一次的改法。但是这样改还并不完全&＃xff0c;因为最终答案会有重复的解答。第二个改法纠结我好久&＃xff1a;最笨的想法是先把解保存在一个 set 集合中&＃xff0c;然后在转入 vector> 中&＃xff0c;但这样太慢了&＃xff0c;不想用。那么是什么原因造成解的重复呢&＃xff1f;原因就是 candidates 数组中包含着重复数&＃xff0c;例如&＃xff1a;

示例1&＃xff1a;candidates &＃61; [10,1,2,7,6,1,5]&＃xff0c;target &＃61; 8&＃xff0c;标准解答&＃xff1a;[[1,2,5],[1,7],[1,1,6],[2,6]]

没有第九行代码前的解答&＃xff1a;[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]&＃xff0c;其中第二个和第四个重复&＃xff0c;第三个和第五个重复。因为数组中有两个1&＃xff0c;这两个1分别组合了一次&＃xff0c;造成了重复。知道原因了&＃xff0c;就好解决&＃xff0c;首先想到的是加入条件candidates[i]&＃61;&＃61;candidates[i-1]当前后元素相等时&＃xff0c;直接跳过本次循环&＃xff0c;但问题又来了&＃xff1a;[1,1,6]这个解&＃xff0c;前后元素相等&＃xff0c;但不重复&＃xff0c;怎么办&＃xff1f;这个我想了好久&＃xff0c;最后看评论&＃xff1a;因为当前层&＃xff0c;如果再取下一个一样的数的话&＃xff0c;就会造成重复&＃xff0c;但是在下一层加入就不会&＃xff0c;因为当前层是替换&＃xff0c;如果拿一个一样的替换肯定会重复。再加入条件&＃xff1a;i>k 就能保证既不会缺少[1,1,6]这个解&＃xff0c;也保证了解的互异。所以第九行加入代码&＃xff1a;if(i>k&&candidates[i]&＃61;&＃61;candidates[i-1])continue;&＃xff0c;然后剩下的剪枝第39题都有。

提交结果&＃xff1a;

个人总结&＃xff1a;

本题和第39题不同&＃xff0c;难度也体现在最后答案的重复上。回溯法的本质还是递归&＃xff0c;递归最难的地方就是容易弄混循环和递归层数&＃xff0c;需要画图仔细分析&＃xff0c;递归循环是个树图&＃xff0c;画图也好容易分析。最后这题也可以不用排序&＃xff0c;因为数字只使用一次&＃xff0c;但是结果是会有重复的&＃xff0c;而且重复的是无规则的&＃xff0c;效率低。