【LeetCode热题100】【回溯】组合总和

题目链接：39. 组合总和 - 力扣（LeetCode）

要找一个和的所有组合，可以从每个数开始深度遍历，在包括自己本身下累加求和，不管行不行都回退状态

优化：每个数从本身开始深度遍历，因为前面的数的组合先前已经找完了

优化：深度遍历前从小到大排序一次，这样可以更快的找到和或者更快的结束

代码语言：javascript复制

class Solution {
public:
    vector<vector<int> > ans;
    vector<int> an;
    vector<int> candidates;
    int target;

    void dfs(int begin, int sum) {
        if (sum == target) {
            ans.push_back(an);
            return;
        } else if (sum > target)
            return;
        for (int i = begin; i < candidates.size();   i) {
            sum  = candidates[i];
            an.push_back(candidates[i]);
            dfs(i, sum);
            an.pop_back();
            sum -= candidates[i];
        }
    }

    vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
        sort(candidates.begin(),candidates.end());
        this->candidates = candidates;
        this->target=target;
        dfs(0, 0);
        return ans;
    }
};

优化 int leetcode 遍历 排序

0 人点赞