题目:40. 组合总和 II
思路
回溯法
(回溯还是很难的,递归不好理解,看着代码很少吧。。。)
代码
class Solution {
public:vector<vector<int>> result;vector<int> path;void function(vector<int>& candidates, int target, int sum, int startindex, vector<bool> used){int i;int size;if(sum == target){result.push_back(path);return;}if(sum > target){return;}size = candidates.size();for(i = startindex; i < size; i++){// used[i-1] == true : path中前面有人使用过;// false : 有别的path使用过 if(i > 0 && candidates[i] == candidates[i-1] && used[i-1] == false){continue;}used[i] = true;sum += candidates[i];path.push_back(candidates[i]);function(candidates, target, sum, i+1, used);used[i] = false;sum -= candidates[i];path.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used (candidates.size(), false);result.clear();path.clear();sort(candidates.begin(), candidates.end());function(candidates, target, 0, 0, used);return result;}
};
难点在于去重,有2个方面的去重,从搜索树上看,
(1)同一层之间的去重;
(2)不同层之间的去重;
用人话来讲:
(1)之前有路径用过这个元素,但和当前路径无关;
(2)当前路径上用过这个元素;
在代码里面用了used
这个变量来辅助去重,按照题目要求,可以出现[1, 1, 6]
,不能出现[1, 7], [1, 7]
(即使里面是2个不同的1
),所以涉及到是去重情况(1);
即无法容忍之前路径上用过同一个元素(可能上述情况(1)(2)两个版本的理解有点不一一对应,总之是这个意思)