Combination Sum

目录

• 题目链接
• 注意点
• 解法
• 小结

题目链接

Combination Sum - LeetCode

注意点

• 数字可以重复使用
• 像这种结果要求返回所有符合要求解的题十有八九都可以用递归

解法

解法一：要先给数组排序，然后遍历，如果当前数字大于target，说明肯定无法组成target，由于排过序，之后的也无法组成target，直接break掉。如果当前数字正好等于target，那么当前单个数字就是一个解，组成一个数组然后放到结果res中。然后我们将当前位置之后的数组取出来，调用递归函数，注意此时的target要减去当前的数字，然后我们遍历递归结果返回的二维数组，将当前数字加到每一个数组最前面，然后再将每个数组加入结果res即可

class Solution {
public:
    vector<vector<int>> combinationSumDfs(vector<int>& candidates, int target,int start)
    {
        vector<vector<int>> ret;
        for(int i = start;i < candidates.size();i++)
        {
            if(candidates[i] > target) break;
            if(candidates[i] == target) 
            {
                ret.push_back({candidates[i]});
                break;
            }
            vector<vector<int>> temp = combinationSumDfs(candidates,target-candidates[i],i);
            for(auto t:temp)
            {
                t.insert(t.begin(),candidates[i]);
                ret.push_back(t);
            }
        }
        return ret;
    }
    vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
        sort(candidates.begin(),candidates.end());
        return combinationSumDfs(candidates,target,0);
    }
};

小结

• 递归的思想