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

剪枝

挖坑