题目：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）两个版本的理解有点不一一对应，总之是这个意思）