LeetCode39——Combination Sum-蒲公英云

LeetCode39——Combination Sum

た入场券 2022-08-09 09:38 126阅读 0赞

LeetCode39——Combination Sum

题意：

打个比方，现在盒子里面有小球，球上有数字，现在给定一个target，要求有放回的从盒子里面取小球，要求数字加起来为target的，把所有加起来为target的组合返回。

这道题的关键就在于数字可以重复取，也就是上述有放回（区别于LeetCode40——Combination Sum II）。

分别以序列中的每一个数字为根，每一层都可以是这个序列的任何数字，从根往下，直到数字加起来大于target（该情况返回上一层），或者等于target（该情况记录结果并返回上一层）。

代码：

class Solution {
private:
    void myFun(int sum,int start, vector<int>temp,vector<int>candidates, vector<vector<int>>&result,int target)
    {
        if (target == sum)
        {
            result.push_back(temp);
            return;
        }
        if (sum > target)
        {
            //temp.pop_back();
            return;
        }
        for (int i = start; i < candidates.size(); i++)
        {
            temp.push_back(candidates[i]);
            myFun(sum + candidates[i],i, temp, candidates, result, target);
            temp.pop_back();//回溯
        }
    }
public:
    vector< vector<int> > combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(), candidates.end());
        candidates.erase(unique(candidates.begin(), candidates.end()),candidates.end());
        vector<vector<int>> result;
        vector<int> temp;
        int start = 0;
        myFun(0, start,temp, candidates, result, target);
        return result;
    }
};