題目（leecode T40）：

給定一個(gè)候選人編號的集合?candidates?和一個(gè)目標(biāo)數(shù)?target?，找出?candidates?中所有可以使數(shù)字和為?target?的組合。

candidates?中的每個(gè)數(shù)字在每個(gè)組合中只能使用?一次?。

注意：解集不能包含重復(fù)的組合。?

方法：本題的要求是每個(gè)元素在組合中只能出現(xiàn)一次，并且候選的數(shù)字是有可能重復(fù)的，因此需要去重操作。分析回溯三部曲。

1：傳入?yún)?shù)與返回值：與組合總和的套路相同，此題還需要加一個(gè)bool型數(shù)組used，用來記錄同一樹枝上的元素是否使用過。這個(gè)集合去重的重任就是used來完成的。

2：終止條件：和組合總和的要求一致，當(dāng)sum值等于target值時(shí)就終止，并且result結(jié)果數(shù)組中收集當(dāng)前path的結(jié)果，如果sum大于了target就直接返回。

3：單層處理邏輯：本題有一個(gè)難點(diǎn)就是因?yàn)樵赜兄貜?fù)所以最終的結(jié)果中我們要去重，有一種方法是算出所有的結(jié)果然后再利用set或map的結(jié)構(gòu)去重，但這種方法容易超時(shí)，因此我們在計(jì)算結(jié)果的過程中就需要去重了。去重具體使用的時(shí)一個(gè)bool類型的used數(shù)組，他記錄著候選數(shù)組中的每個(gè)元素的值是否使用過了。具體邏輯入代碼所示、

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {if (sum == target) {result.push_back(path);return;}for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {// used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過// used[i - 1] == false，說明同一樹層candidates[i - 1]使用過// 要對同一樹層使用過的元素進(jìn)行跳過if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {continue;}sum += candidates[i];path.push_back(candidates[i]);used[i] = true;backtracking(candidates, target, sum, i + 1, used); // 和39.組合總和的區(qū)別1，這里是i+1，每個(gè)數(shù)字在每個(gè)組合中只能使用一次used[i] = false;sum -= candidates[i];path.pop_back();}}public:vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {vector<bool> used(candidates.size(), false);path.clear();result.clear();// 首先把給candidates排序，讓其相同的元素都挨在一起。sort(candidates.begin(), candidates.end());backtracking(candidates, target, 0, 0, used);return result;}
};