首页 > itarticle > leetcode 题目描述：解题思路：

leetcode 题目描述：解题思路：

admin 11月 14, 2020 0

39. 组合总和

题目描述：

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

所有数字（包括 target）都是正整数。
解集不能包含重复的组合。

示例 1:

输入: candidates = [2,3,6,7], target = 7,
所求解集为:
[
  [7],
  [2,2,3]
]

解题思路：

很清晰的一个递归题目，通过递归即可求解，注意数组中所有比target的数都没有任何作用，所以先将数组排序，然后去除所有比target大的数，这样可以很大的缩短运行时间

代码：

class  {
public:
    void combinationSumnew(vector<vector<int>>& result,vector<int>& solution,vector<int> candidates,int start,int end,int target){
        
        if(target < 0){
            return;
        }
        //找到了一组solution
        if(target == 0){
            result.push_back(solution);
            return;
        }

        for(int i = start; i <= end; i++){
            if(candidates[i] > target){
                return;
            }
            solution.push_back(candidates[i]);
            //递归调用
            combinationSumnew(result,solution,candidates,i,end,target-candidates[i]);
            solution.pop_back();
        }
    }
    
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        vector<vector<int>>  result;       
        if(candidates.size() == 0){
            return result;
        }
        sort(candidates.begin(),candidates.end());
        //剪掉所有比target大的数
        int end = candidates.size() - 1;
        
        while(end > 0 && candidates[end] > target){
            end--;
        }
        
        vector<int> solution;
        combinationSumnew(result,solution,candidates,0,end,target);
        return result;    
    }
       

};