Leetcode|组合|77. 组合（first索引+索引距离n＞还需元素个数剪枝）

文章目录

• • 1 回溯法（first索引）
  • 2 回溯法（first索引 索引距离n>还需元素个数剪枝）

1 回溯法（first索引）

代码语言：javascript复制

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

2 回溯法（first索引 索引距离n>还需元素个数剪枝）

本题可以加上剪枝，从而提高回溯效率

i表示组合中的第1个元素, 若索引i距离n不到所需元素个数(k - path.size())则break

代码语言：javascript复制

for (int i = first; i < n; i  )
// 变为↓
for (int i = first; i <= n - (k - path.size()); i  )

完整代码如下

代码语言：javascript复制

class Solution {
private:
    vector<vector<int>> solution;
    vector<int> path;
public:
    void backtrack(int n, int k, int first) {
        if (path.size() == k) {
            solution.emplace_back(path);
            return;
        }
        /**i表示组合中的第1个元素, 若索引i距离n不到所需元素个数(k - path.size())则break**/
        for (int i = first; i <= n - (k - path.size()); i  ) {
            path.emplace_back(i   1);  // 初始索引first=0, 组合元素需 1
            backtrack(n, k, i   1);
            path.pop_back();
        }
    }
    vector<vector<int>> combine(int n, int k) {
        backtrack(n, k, 0);
        return solution;
    }
};

break path size 索引 效率

0 人点赞