題目（leecode T40）：

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

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

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

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

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

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

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

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]使用過// 要對同一樹層使用過的元素進行跳過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，每個數(shù)字在每個組合中只能使用一次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;}
};