【LeetCode】Combination Sum(组合总和)

这道题是LeetCode里的第39道题。

题目描述：

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

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

说明：

所有数字（包括 target）都是正整数。

解集不能包含重复的组合。

示例 1:
输入: candidates = [2,3,6,7], target = 7,

所求解集为:

[

  [7],

  [2,2,3]

]
示例 2:
输入: candidates = [2,3,5], target = 8,

所求解集为:

[

  [2,2,2,2],

  [2,3,3],

  [3,5]

]

首先一看到题目我能想到的就是递归，但感觉递归太简单实现了，而且递归函数参数多(想起八皇后问题)，想试试别的方法，一看评论区，绝大多数都是回溯剪枝法，递归法，DFS。其实一看代码其实这三种方法几乎一样。

示例二图：

当总和大于等于8时，就可以剪枝了，也就是说后面已经没有了答案。

解题代码：

class Solution {

public:

    vector<vector<int>> res;

    vector<int> ans;

    void getres(vector<int>& candidates,int target,int k,vector<int> ans){

        int size=candidates.size();

        for(int i=k;i<size;i++){

            if(target-candidates[i]>0){

                ans.push_back(candidates[i]);

                getres(candidates,target-candidates[i],i,ans);

                ans.pop_back();

            }

            else if(target-candidates[i]<0){return;}

            else{

                ans.push_back(candidates[i]);

                res.push_back(ans);

                ans.pop_back();

                return;

            }

        }

        return;

    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        sort(candidates.begin(),candidates.end());

        getres(candidates,target,0,ans);

        return res;

    }

};

然后想优化代码，优化就是为了剪枝，缩短运行时间。以下是优化结果，但是运行结果是错的。原因在于我之前写的代码已经具备的剪枝的效果，我后面这样写画蛇添足了。

class Solution {

public:

    vector<vector<int>> res;

    vector<int> ans;

    bool getres(vector<int>& candidates,int target,int k,vector<int> ans){

        int size=candidates.size();

        for(int i=k;i<size;i++){

            if(target-candidates[i]>0){

                ans.push_back(candidates[i]);

                if(getres(candidates,target-candidates[i],i,ans)){

                    ans.pop_back();

                    return false;

                }

                ans.pop_back();

            }

            else if(target-candidates[i]<0){return true;}

            else{

                ans.push_back(candidates[i]);

                res.push_back(ans);

                ans.pop_back();

                return false;

            }

        }

        return false;

    }

    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {

        sort(candidates.begin(),candidates.end());

        getres(candidates,target,0,ans);

        return res;

    }

};

提交结果：

个人总结：

本题的数据是可以重复的，可重复加深了答案的深度。还有我一开始没有对数据进行排序，导致一次错误，如果不排序的话，想要得出答案会很麻烦，剪枝步骤也会变得毫无意义，尤其是在大数据下，对数据进行先排序后处理，时间上的优势可以明显的表现出来。

巴特西