day24 | 回溯1

0.引言

1.理论基础

• 参考

77.# 组合

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

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

示例 1：

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

输入：n = 1, k = 1
输出：[[1]]

提示：

• 1 <= n <= 20
• 1 <= k <= n

Discussion | Solution

回溯

起始本质都是递归都是深搜

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

// @lc code=start
class Solution {
 public:
  vector<vector<int>> combine(int n, int k) {
    std::vector<int> one_combine;
    std::vector<std::vector<int>> res;
    dfs(n, k, one_combine, res, 1);
    return res;
  }

 private:
  void dfs(int n, int k, std::vector<int>& one_combine,
           std::vector<std::vector<int>>& res, int start_idx) {
    if (one_combine.size() == k) {
      res.push_back(one_combine);
      return;
    }

    for (int i = start_idx; i <= n; ++i) {
      one_combine.push_back(i);
      dfs(n, k, one_combine, res, i + 1);  // i 为隐式回溯
      one_combine.pop_back();
    }
  }
};
// @lc code=end

剪枝

挖坑