Leetcode|组合|216.组合总和III（first+右分支收紧）

1 回溯法（first 右分支收紧）

有了前2道组合总和问题，再看第三道组合总和问题，简直就是弟弟，记住，排列组合子集三个问题的三板斧就是first，inPath和sort 跳过重复元素，本问题仅用first足矣

代码语言：javascript复制

class Solution {
private:
    int size = 10;
    vector<vector<int>> solution;
    vector<int> path;
public:
    void backtrack(int k, int n, int sum, int first) {
        if (path.size() > k) return;
        if (sum == n && path.size() == k) {
            solution.emplace_back(path);
            return;
        }
        for (int i = first; i < size; i  ) {
            if (sum   i > n) break;
            path.emplace_back(i);
            backtrack(k, n, sum   i, i   1);
            path.pop_back();
        }
    }
    vector<vector<int>> combinationSum3(int k, int n) {
        backtrack(k, n, 0, 1);
        return solution;
    }
};

轻松首次提交就AC(▽)

sort

0 人点赞