一、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(); } }新闻热点
疑难解答
