Day21- 回溯算法part01

一、组合

题目一：77. 组合

77. 组合

给定两个整数?n?和?k，返回范围?[1, n]?中所有可能的?k?个数的组合。

你可以按?任何顺序?返回答案

combine 函数初始化结果变量和当前组合变量，然后调用 backtrack 函数来生成所有组合。backtrack 函数通过添加当前元素到组合中，然后递归地调用自身来添加下一个元素，来生成组合。当组合的大小达到 k 时，它会被添加到结果列表中。

在回溯过程中，最近添加的元素会被移除，以便于尝试下一个可能的元素。

/*
 * @lc app=leetcode.cn id=77 lang=cpp
 *
 * [77] 组合
 */

// @lc code=start
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> result;
        vector<int> combination;
        backtrack(result, combination, 1, n, k);
        return result;
    }

    void backtrack(vector<vector<int>>& result, vector<int>& combination, int start, int n, int k) {
        if (combination.size() == k) {
            result.push_back(combination);
            return;
        }

        for (int i = start; i <= n; ++i) {
            combination.push_back(i);
            backtrack(result, combination, i + 1, n, k);
            combination.pop_back();
        }
    }
};
// @lc code=end