题目描述
给两个整数 n 和 k，返回 1..n 中所有 k 个数的组合（组合不讲顺序，[1,2] 和 [2,1] 算同一个）。
n = 4
k = 2
输出 = [1,2][1,3][1,4][2,3][2,4][3,4]
思路解析
k=2 写两层 for，k=5 写五层……k 是变量时，嵌套循环根本写不出来。
用递归代替「不定层循环」：每选一个数，就从它后面继续选下一个，选够 k 个就收下。
关键是 start：选了 2 之后只能从 3 往后挑，绝不回头选 1。这样 [1,2] 出现过就不会再冒出 [2,1]。
选 1：先选 1，路径 [1]。接下来只能从 2 开始往后挑，1 不再回头看。
选 2，凑够 2 个：再选 2，路径 [1,2]，已经够 k=2 个，收进结果，然后回退换下一个。
回溯，1 配 3、配 4：退回去把 1 跟 3、跟 4 也配一遍，收下 [1,3]、[1,4]。1 打头的组合就全了。
换头：2、3 打头：再回到最外层换成 2 打头、3 打头……最终 6 个组合全部收齐。
组合类题的核心——用 start 下标避免重复，让不定层数的枚举变成一个干净的递归。
参考代码（Python）
Python
1def combine(n, k):
2 res = []
3 def bt(start, path):
4 if len(path) == k: # 够 k 个，收
5 res.append(path[:]); return
6 for i in range(start, n + 1): # 从 start 往后挑
7 path.append(i)
8 bt(i + 1, path) # 下一层从 i+1 开始
9 path.pop() # 撤销，回溯
10 bt(1, [])
11 return res复杂度分析
- 时间复杂度：O(C(n,k) · k) —— 收每个组合要 O(k)
- 空间复杂度：O(k) —— 递归深度 k
套路模板
骨架记牢：for 从 start 起、递归传 i+1（不是 start+1）、选完 pop。这是所有「组合 / 子集」题的母模板。
Python
1def bt(start, path):
2 if 满足收集条件:
3 res.append(path[:]); return
4 for i in range(start, n + 1):
5 path.append(i)
6 bt(i + 1, path) # 关键：i+1
7 path.pop()易错点
- ❌ 下一层传 start + 1 → ✅ 传 i + 1（要从「当前选的 i」后面继续，不是从 start 后面，传 start+1 会重复选）
- ❌ res.append(path) → ✅ res.append(path[:])（path 是同一个列表，会被后续 pop 改掉，必须存一份拷贝）
- ❌ 选完忘了 path.pop() → ✅ 递归后立刻 pop 撤销（不撤销，path 会越积越长，把别的分支也污染了）
以上文字与上方动画完全同一思路：先看动画建立直觉 → 读文字巩固 → 关掉页面自己默写一遍代码，能写出来才算真的掌握。