題目

給定一個(gè)數(shù)組 candidates 和一個(gè)目標(biāo)數(shù) target ，找出 candidates 中所有可以使數(shù)字和為 target 的組合。
candidates 中的每個(gè)數(shù)字在每個(gè)組合中只能使用一次。

思考以及代碼

如果我們直接套用39題的思路，那么就會出現(xiàn)重復(fù)的組合。

重復(fù)組合的產(chǎn)生，是因?yàn)榧现杏兄貜?fù)的元素。
去重，就是使用過的元素不能重復(fù)選取。
我們r(jià)esult的重復(fù)組合的產(chǎn)生肯定是和重復(fù)元素有關(guān)的，我們從解空間樹的深度(遞歸調(diào)用)和寬度(for循環(huán))來看：
1、元素的重復(fù)的影響可能出現(xiàn)在在解空間樹的寬度和深度上。
2、寬度上的重復(fù)決定了我們r(jià)esult解的組合的重復(fù)，深度上的重復(fù)決定了result解的每個(gè)子結(jié)果res的元素重復(fù)。
3、結(jié)合題意：如果是在寬度上重復(fù)我們需要去除，如果是在深度上重復(fù)我們不需要去除。

在寬度上進(jìn)行去重所以我們在for循環(huán)的過程中加入限制。

//如果遇到同一個(gè)集合的重復(fù)元素，跳過這個(gè)元素即可 if(i > startindex && candidates[i] == candidates[i-1]) continue;

注意這里我們已經(jīng)對原數(shù)組進(jìn)行排序了，所以重復(fù)的元素一定靠在一起

class Solution { public:vector<vector<int>> result;vector<int> res;int sum;void clear_solution_param(){result.clear();res.clear();sum=0;}void backtracking(vector<int>& candidates,int startindex,int n){ if(sum > n) return;if(sum == n){result.push_back(res);return;}for(int i=startindex;i<candidates.size();i++){//由于輸入的數(shù)組是有序的，所以直接進(jìn)行剪枝。如果sum加上這個(gè)集合元素大于目標(biāo)，此層就不需要往后看了，因?yàn)楹竺娴脑丶由蟬um肯定大于目標(biāo)if(sum+candidates[i]>n) break;//如果遇到同一個(gè)集合的重復(fù)元素，跳過這個(gè)元素即可if(i > startindex && candidates[i] == candidates[i-1]) continue;//處理結(jié)點(diǎn)；res.push_back(candidates[i]);sum+=candidates[i];//遞歸,探索下一層backtracking(candidates,i+1,n); //遞歸sum-=candidates[i];//回溯，撤銷處理結(jié)果res.pop_back();}}vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {clear_solution_param();//排序加速剪枝sort(candidates.begin(),candidates.end());backtracking(candidates,0,target);return result;} };

總結(jié)

以上是生活随笔為你收集整理的leetcode 40. 组合总和 II 思考分析的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。