一、39. Combination Sum Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. The same repeated number may be chosen from C unlimited number of times. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [2, 3, 6, 7] and target 7, A solution set is: [ [7], [2, 2, 3] ]
vector<vector<int>> combinationSum(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int>> res; vector<int> combination; combinationSum(candidates,target,res,combination,0); return res; } void combinationSum(vector<int>& candidates, int target,vector<vector<int>> &res,vector<int>& combination,int begin){ if(!target){ //當target為0的時候，就將combination壓入res中，函數返回 res.push_back(combination); return; } for(int i = begin; i != candidates.size() && target >= candidates[i]; i++){ combination.push_back(candidates[i]); combinationSum(candidates,target - candidates[i] ,res,combination,i); //注意在Combination Sum中允許出現重復的數據，所以最后遞歸是從i開始，此外是從給出的candidates中查找滿足條件的組合，所以第一個參數為candidates combination.pop_back(); } }二、40. Combination Sum II Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: All numbers (including target) will be positive integers. The solution set must not contain duplicate combinations. For example, given candidate set [10, 1, 2, 7, 6, 1, 5] and target 8, A solution set is: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) { sort(candidates.begin(),candidates.end()); vector<vector<int>> res; vector<int> combination; combinationSum(candidates,target,res,combination,0); return res; } void combinationSum(vector<int>& candidates, int target,vector<vector<int>> &res,vector<int>& combination,int begin){ if(!target){ //當target為0的時候，就將combination壓入res中，函數返回 res.push_back(combination); return; } for(int i = begin; i != candidates.size() && target >= candidates[i]; i++){ //如果不加if語句的話對于：[10,1,2,7,6,1,5] 8的實例程序會輸出：[[1,1,6],[1,2,5],[1,7],[1,2,5],[1,7],[2,6]]，會存在重復，但期望輸出：[[1,1,6],[1,2,5],[1,7],[2,6]]，所以假如if條件 if(i == begin || candidates[i] != candidates[i-1]){ combination.push_back(candidates[i]); combinationSum(candidates,target - candidates[i] ,res,combination,i+1); //注意在Combination SumII中不允許同一個數出現兩次及以上，所以最后遞歸是從i+1開始，此外是從給出的candidates中查找滿足條件的組合，所以第一個參數為candidates combination.pop_back(); } } }三、216. Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. Example 1: Input: k = 3, n = 7 Output: [[1,2,4]] Example 2: Input: k = 3, n = 9 Output: [[1,2,6], [1,3,5], [2,3,4]]
vector<vector<int>> combinationSum3(int k, int n) { //sort(candidates.begin(),candidates.end()); vector<vector<int>> res; vector<int> combination; combinationSum(n,res,combination,1,k); return res; } void combinationSum(int target, vector<vector<int>> &res,vector<int>& combination,int begin,int need){ if(!target){ //當target為0的時候，就將combination壓入res中，函數返回 res.push_back(combination); return; } else if(!need) return; for(int i = begin; i != 10 && target >= i * need + need *(need - 1) / 2; i++){ combination.push_back(i); combinationSum(target - i ,res,combination,i+1,need-1); //注意在Combination SumIII中不允許同一個數出現兩次及以上，所以最后遞歸是從i+1開始，以及加入一個數進去后，需要的數會減少，所以是need - 1 combination.pop_back(); } }也可以改變for循環條件，更加易懂，代碼變為：
vector<vector<int>> combinationSum3(int k, int n) { //sort(candidates.begin(),candidates.end()); vector<vector<int>> res; vector<int> combination; combinationSum(n,res,combination,1,k); return res; } void combinationSum(int target, vector<vector<int>> &res,vector<int>& combination,int begin,int k){ if(!target && k == 0){ //當target為0的時候，就將combination壓入res中，函數返回 res.push_back(combination); return; } /*else if(!need) return;*/ for(int i = begin; i <= 10 - k && target >= i; i++){ combination.push_back(i); combinationSum(target - i ,res,combination,i+1,k-1); //注意在Combination SumIII中不允許同一個數出現兩次及以上，所以最后遞歸是從i+1開始，以及加入一個數進去后，需要的數會減少，所以是k - 1 combination.pop_back(); } }新聞熱點
疑難解答
