LeetCode 77中等回溯 · 组合
组合 图解题解
这道题到底在问什么
给两个整数 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]
先想最直接的笨办法
组合类题的核心——用 start 下标避免重复，让不定层数的枚举变成一个干净的递归。（动画第 15 步）
最优解：一步一步想明白
- 3k=2 写两层 for，k=5 写五层……k 是变量时，嵌套循环根本写不出来。
- 4转折：用递归代替「不定层循环」。每选一个数就从它后面继续选（start 保证只往后、天然去重，[1,2] 不会再冒出 [2,1]）；选够 k 个就收进结果，然后撤销刚才那一步（path.pop）回到上层，换下一个候选。选→递归→撤销，三步循环。
- 5从 2 往后选先选 1，path=[1]。接下来 start=2，只能从 2 往后挑，1 不再回头看。还没够 k=2 个，继续往下选。
- 6len(path)==k，收下 [1,2]再选 2，path=[1,2]，长度到 k=2，收进结果 [1,2]。这条分支到头了，该回退。
- 7path.pop() → [1]负例/回溯动作：把刚选的 2 弹出，path 退回 [1]，2 重新变回「可选」。不撤销的话 path 会越积越长、污染后面的分支。回到上层接着试下一个候选。
- 8收下 [1,3]在 [1] 基础上改选 3，path=[1,3]，够 2 个，收下 [1,3]。再撤销 3、改选 4……
- 91 打头的全收齐同理收下 [1,4]。1 后面 2、3、4 都配过了，1 打头的组合全齐。接着把 1 也撤销，换头。
- 10path=[2,3]回到最外层，改用 2 打头（start=3），收 [2,3]。注意 1 已撤销、不在 path 里——start 保证不会再回头配到 1。
- 11path=[2,4]撤销 3、改选 4，收 [2,4]。2 打头的也配完了，再撤销 2 换成 3 打头。
- 12C(4,2) = 63 打头收下 [3,4]。（4 打头后面没数了，凑不齐 2 个，是条死分支，直接返回。）最终 6 个组合全部收齐。
- 15组合类题的核心——用 start 下标避免重复，让不定层数的枚举变成一个干净的递归。
⚠️ 容易写错的地方
✗ 错：下一层传 start + 1
✓ 对：传 i + 1
要从「当前选的 i」后面继续，不是从 start 后面，传 start+1 会重复选
✗ 错：res.append(path)
✓ 对：res.append(path[:])
path 是同一个列表，会被后续 pop 改掉，必须存一份拷贝
✗ 错：选完忘了 path.pop()
✓ 对：递归后立刻 pop 撤销
不撤销，path 会越积越长，把别的分支也污染了
完整代码（Python）
Python
class Solution:
def combine(self, n, k):
ans = []
def backtrack(start, path):
if len(path) == k:
ans.append(path[:])
return
for x in range(start, n + 1):
path.append(x)
backtrack(x + 1, path)
path.pop()
backtrack(1, [])
return ans套路模板 · 组合回溯（背下来）
def bt(start, path):
if 满足收集条件:
res.append(path[:]); return
for i in range(start, n + 1):
path.append(i)
bt(i + 1, path) # 关键：i+1
path.pop()复杂度
时间复杂度
O(C(n,k) · k)
收每个组合要 O(k)
空间复杂度
O(k)
递归深度 k
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 组合 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这道题为什么用「组合」，换最直接的暴力解会差在哪？+
组合抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
时间复杂度为什么是 undefined？怎么推出来的？+
按上文复杂度小节的推导，时间复杂度为 undefined。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。