组合问题如何用回溯生成？为什么递归要传 start？

简化版

组合问题用 start 控制下一层只能从后面的数字继续选，避免 [1,2] 和 [2,1] 这种顺序重复。每次选择一个数加入路径，递归进入下一层；路径长度达到 k 时收集答案，再撤销选择回到上一层。

详细版

组合和排列的最大区别是：组合不关心选择顺序。因此搜索树不能每层都从 1 开始枚举，而要让下一层从 i + 1 开始，这样路径天然保持递增，保证每个组合只出现一次。

如果题目是从 1..n 中选 k 个数，递归状态通常是 backtrack(start, path)。当 path.size() == k 时复制路径加入结果。剪枝点是：如果剩余可选数字数量已经不足以补满 k，就没必要继续枚举，循环上界可以写成 i <= n - (k - path.size()) + 1。

复杂度约为 O(C(n,k) * k)，因为最终有 C(n,k) 个结果，每个结果复制长度为 k。递归额外空间是 O(k)，不计输出空间。

完整版教学

一、组合问题到底在去掉什么重复

给定 n = 4, k = 2，合法组合是：

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

如果像排列那样每层都从 1 开始枚举，会产生 [1,2] 和 [2,1]。它们选择的元素集合一样，只是顺序不同；组合题要求把它们视作同一个答案。

因此组合回溯的核心不是 used[]，而是 start：它规定下一层只能从当前选择之后的位置继续选。

选择 1 后：只能选 2、3、4
选择 2 后：只能选 3、4
选择 3 后：只能选 4

二、为什么递归参数是 start 而不是 used

排列题需要 used[]，因为每个位置都可以放任意未使用元素，顺序有意义。组合题只需要 start，因为我们人为规定路径递增，顺序被固定住了。

问题类型	是否关心顺序	常见状态	下一层枚举范围
排列	关心	`used[]`	从 1 到 n 扫所有未用数
组合	不关心	`start`	从 `start` 到 n
子集	不关心	`start`	从 `start` 到 n，长度不固定

记忆钩子：排列靠 used 防止重复使用，组合靠 start 防止顺序重复。

三、搜索树怎么展开

以 n = 4, k = 2 为例，搜索树可以画成：

[]
├─ 1
│  ├─ 2 -> [1,2]
│  ├─ 3 -> [1,3]
│  └─ 4 -> [1,4]
├─ 2
│  ├─ 3 -> [2,3]
│  └─ 4 -> [2,4]
└─ 3
   └─ 4 -> [3,4]

注意根节点不需要从 4 开始，因为选了 4 后已经没有数字能补出长度为 2 的组合。这个观察会引出剪枝。

四、剪枝上界如何推出来

假设当前路径长度是 path.size()，还需要 need = k - path.size() 个数。当前准备枚举数字 i，从 i..n 一共有 n - i + 1 个可选数字。若 n - i + 1 < need，即剩余数字不够，就可以停止。

变形得到：

n - i + 1 >= need
i <= n - need + 1
need = k - path.size()

所以循环可以写成：

for (int i = start; i <= n - (k - path.size()) + 1; i++) {
    ...
}

例如 n=5, k=3，当路径为空时还需要 3 个数，第一层 i 最大只能到 5 - 3 + 1 = 3，因为从 4 开始只剩 [4,5] 两个数，无法凑满 3 个。

五、代码模板

组合代码的关键是“选择、递归、撤销”三步，收集答案时必须复制路径。

List<List<Integer>> combine(int n, int k) {
    List<List<Integer>> res = new ArrayList<>();
    backtrack(1, n, k, new ArrayList<>(), res);
    return res;
}

void backtrack(int start, int n, int k, List<Integer> path, List<List<Integer>> res) {
    if (path.size() == k) {
        res.add(new ArrayList<>(path));
        return;
    }
    int need = k - path.size();
    for (int i = start; i <= n - need + 1; i++) {
        path.add(i);
        backtrack(i + 1, n, k, path, res);
        path.remove(path.size() - 1);
    }
}

这份模板适合大多数“不重复选、顺序无关”的组合枚举题。若元素来自数组而不是 1..n，把 i 当作数组下标即可。

六、复杂度为什么和答案数量相关

组合题无法比输出规模更快，因为结果本身就有 C(n,k) 个。每次收集答案要复制长度为 k 的路径，所以输出相关复杂度是：

时间复杂度：O(C(n,k) * k)
递归深度：O(k)
输出空间：O(C(n,k) * k)

面试中不要只说“指数级”。更准确的说法是：搜索树被 start 和剪枝约束后，真正落到答案的叶子数量就是组合数，算法主要成本来自枚举并复制所有组合。

七、常见误区与追问

误区：组合题也必须用 used 数组。 对 1..n 选 k 这类题，start 已经保证不重复使用和不产生顺序重复。
误区：递归下一层传 i。 传 i 会允许当前数字再次被选择，变成可重复选择的组合总和模型。
误区：结果中直接加入 path。 path 后续会被修改，必须 new ArrayList<>(path) 复制快照。
追问：剪枝上界怎么写？ 当前还需要 need 个数，必须保证 i..n 至少有 need 个，所以 i <= n - need + 1。
追问：它和子集题有什么区别？ 子集每个节点都可收集答案，组合只在路径长度等于 k 时收集。
追问：如果数组有重复值怎么办？ 先排序，再在同一层跳过 i > start && nums[i] == nums[i - 1]。

八、加强记忆

组合题可以记成“固定顺序的选择树”：为了让 [1,2] 和 [2,1] 不重复出现，路径只允许往右走，所以递归状态一定要带 start。写代码时先确定终止条件 path.size() == k，再写循环 i from start，最后用“剩余数量够不够”推导剪枝上界。只要能讲清楚 start 防顺序重复、i + 1 防重复使用、复制路径防引用污染，组合类回溯就基本答稳了。

简化版

详细版