05、组合

从 1 到 n 选 k 个数，选择的先后顺序不产生新答案。解决组合问题的关键，是让候选下标只向前推进，再判断剩余候选是否足够填满答案。

问题与目标

LeetCode 77：组合要求返回 [1,n] 中所有长度为 k 的组合。例如 n = 4, k = 2：

[1,2] [1,3] [1,4] [2,3] [2,4] [3,4]

[2,1] 不再生成，因为它和 [1,2] 是同一个组合。与子集不同，这里只收集长度恰好为 k 的路径。

起点只前进，避免顺序重复

递归参数 start 表示本层最小可选数。选了 i，下一层从 i + 1 开始。因此路径始终严格递增，不需要额外的 used 数组。

路径已有 m 个数时，还需要 need = k - m 个。如果当前准备选 i，那么从 i 到 n 一共还有 n - i + 1 个数。只有它不少于 need 时才可能成功：

i <= n - need + 1

这就是循环上界的来源。它是在数“还剩几个候选”，不是一个需要死记的减法公式。

用 n=4、k=2 核对剪枝

空路径还需要两个数，首个选择最大只能是 3；选择 4 后已经没有后继，必定凑不够两个，所以不必进入这个分支。

选择 3 后只需要一个数，下一层可以选择 4，得到 [3,4]。这也说明不能固定把所有层的上界都写成 n-k+1：需要的数量随路径长度变化。

C++17 实现

#include <vector>

class Solution {
 public:
  std::vector<std::vector<int>> combine(int n, int k) {
    if (n < 0 || k < 0 || k > n) return {};
    std::vector<std::vector<int>> answers;
    std::vector<int> path;
    search(n, k, 1, path, answers);
    return answers;
  }

 private:
  void search(int n, int k, int start, std::vector<int>& path,
              std::vector<std::vector<int>>& answers) {
    if (path.size() == static_cast<std::size_t>(k)) {
      answers.push_back(path);
      return;
    }
    const int need = k - static_cast<int>(path.size());
    for (int value = start; value <= n - need + 1; ++value) {
      path.push_back(value);
      search(n, k, value + 1, path, answers);
      path.pop_back();
    }
  }
};

复杂度与边界

共有 C(n,k) 个答案，复制每个答案需要 O(k)。有效 k 的情况下，总时间为 O(k·C(n,k))；辅助路径和递归栈为 O(k)，结果空间另计。

题目范围内 1 <= k <= n。实现额外约定 k = 0 返回一个空组合 [[]]；k > n、负参数返回空结果。k=0 的返回成本单独为常量。

常见误区

下一层仍从 i 开始，会允许重复选择同一个数；从 1 重新开始会生成排列；每进入一个节点就保存路径，则变成了子集问题。回溯代码虽然相似，候选范围和收集条件却决定了完全不同的题意。