题型地图 56天全屏 141题

当前：LC77 · 组合 · 首次出现于 Day 26 · 路径：顶栏「56天打卡」→ 点击 LC 题号 → 逐题动画

31 / 141回到 Day 26 卡片 141 题索引

Combination Squad Lab

LC77 组合：从候选名单里选出所有 k 人小队

关键不是暴力枚举，而是用 start 规定「只能向后选」，让每个组合只出现一次。

时间复杂度

O(C(n,k) × k)

要输出 C(n,k) 个组合，每个复制 k 个数。

辅助空间

O(k)

path 长度最多 k，递归栈深度最多 k。

输出空间

O(C(n,k) × k)

n=4,k=2 时结果篮里共 6 张组合卡。

hero · 1/35

Candidates

n=4 候选队员

从 1..4 中选 2 人组成小队，顺序不重要。

Result Basket

结果篮

[?,?]

Combo vs Perm

组合 vs 排列

合法组合

[1,2]

从小到大选，只保留一次

倒序写法（非法）

[2,1]

排列才会保留 [2,1]

规则：只允许从小到大选 → 代码里用 start 保证「选过 i 后，只能从 i+1 继续」。

Start Gate

start 单向闸门

path

[]

start

可选

1, 2, 3, 4

hero

组合组队实验室

有 4 名候选队员 1、2、3、4，要组一支 2 人小队。组合不看顺序，所以最终只有 6 种不同小队。

关键不是暴力枚举所有排列，而是用 start 规定「只能向后选」，让每个组合只出现一次。

path

[]

start

ans

[]

Squad Tree

组队树 n=4, k=2

[]

├─ 选 1 → [1]

│ ├─ 选 2 → [1,2] ✅

│ ├─ 选 3 → [1,3] ✅

│ └─ 选 4 → [1,4] ✅

├─ 选 2 → [2]

│ ├─ 选 3 → [2,3] ✅

│ └─ 选 4 → [2,4] ✅

├─ 选 3 → [3]

│ └─ 选 4 → [3,4] ✅

└─ 选 4 → [4] ❌

Go Code

代码与动画同步

1func combine(n int, k int) [][]int {
2    ans := make([][]int, 0)
3    path := make([]int, 0, k)
4 
5    var backtrack func(start int)
6    backtrack = func(start int) {
7        if len(path) == k {
8            tmp := make([]int, k)
9            copy(tmp, path)
10            ans = append(ans, tmp)
11            return
12        }
13 
14        need := k - len(path)
15 
16        for i := start; i <= n-need+1; i++ {
17            path = append(path, i)
18            backtrack(i + 1)
19            path = path[:len(path)-1]
20        }
21    }
22 
23    backtrack(1)
24    return ans
25}

path = append(path, i)把编号 i 的队员加入当前小队。
backtrack(i + 1)单向闸门移到 i 后面：下一层只能从 i+1 继续选。
path = path[:len(path)-1]撤销选择，回到上一层继续试下一个 i。
copy(tmp, path)必须复制 path；否则后续回溯会改掉已收集的答案。
i <= n-need+1剪枝上界：剩余可选人数必须 ≥ 还需要的人数 need。

Prune Radar

余量雷达 · 剪枝

need = k - len(path)

还需要选几人

remain = n - i + 1

从 i 到 n 还能选几人

判定

剪枝

remain < need 则必死

for i := start; i <= n-(k-len(path))+1; i++ {
  // n=4, k=3, path=[3], need=2, i=4
  // remain = 4-4+1 = 1 < 2 → 不进入循环

剩余人数不够，整条分支变红 —— 直接剪枝，不必再递归。

Trace

执行轨迹表

Step	start	i	path	action	ans
1	start=1	-	[] → []	backtrack(1) 入口	[]
2	start=1	i=1	[] → [1]	选择 1	[]
3	start=2	i=2	[1] → [1,2]	选择 2	[]
4	start=3	-	[1,2] → [1,2]	达到 k，收集	[[1,2]]
5	start=2	i=2	[1,2] → [1]	回溯，撤销 2	[[1,2]]
6	start=2	i=3	[1] → [1,3]	选择 3	[[1,2]]
7	start=4	-	[1,3] → [1,3]	达到 k，收集	[[1,2], [1,3]]
8	start=2	i=3	[1,3] → [1]	回溯，撤销 3	[[1,2], [1,3]]
9	start=2	i=4	[1] → [1,4]	选择 4	[[1,2], [1,3]]
10	start=5	-	[1,4] → [1,4]	达到 k，收集	[[1,2], [1,3], [1,4]]
11	start=2	i=4	[1,4] → [1]	回溯，撤销 4	[[1,2], [1,3], [1,4]]
12	start=1	i=1	[1] → []	回溯，撤销 1	[[1,2], [1,3], [1,4]]
13	start=1	i=2	[] → [2]	选择 2	[[1,2], [1,3], [1,4]]
14	start=3	i=3	[2] → [2,3]	选择 3	[[1,2], [1,3], [1,4]]
15	start=4	-	[2,3] → [2,3]	达到 k，收集	[[1,2], [1,3], [1,4], [2,3]]
16	start=3	i=3	[2,3] → [2]	回溯，撤销 3	[[1,2], [1,3], [1,4], [2,3]]
17	start=3	i=4	[2] → [2,4]	选择 4	[[1,2], [1,3], [1,4], [2,3]]
18	start=5	-	[2,4] → [2,4]	达到 k，收集	[[1,2], [1,3], [1,4], [2,3], [2,4]]
19	start=3	i=4	[2,4] → [2]	回溯，撤销 4	[[1,2], [1,3], [1,4], [2,3], [2,4]]
20	start=1	i=2	[2] → []	回溯，撤销 2	[[1,2], [1,3], [1,4], [2,3], [2,4]]
21	start=1	i=3	[] → [3]	选择 3	[[1,2], [1,3], [1,4], [2,3], [2,4]]
22	start=4	i=4	[3] → [3,4]	选择 4	[[1,2], [1,3], [1,4], [2,3], [2,4]]
23	start=5	-	[3,4] → [3,4]	达到 k，收集	[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
24	start=4	i=4	[3,4] → [3]	回溯，撤销 4	[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
25	start=1	i=3	[3] → []	回溯，撤销 3	[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]
26	start=4	i=4	[4] → [4]	人数不够，分支结束	[[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

完整轨迹共 26 步（组队树模块自动生成）。

Interview

面试表达

这题用回溯枚举所有长度为 k 的组合。path 保存当前已经选择的数字，start 表示下一次只能从哪个数字开始选。每次选择 i 后递归到 i+1，保证 path 严格递增，因此不会出现 [1,2] 和 [2,1] 这种重复组合。当 path 长度等于 k 时复制进答案。为了减少无效搜索，可以根据还需要选择的人数 need，限制循环上界为 n-need+1，避免剩余数字不够时继续递归。时间复杂度 O(C(n,k) × k)，辅助空间 O(k)，输出空间 O(C(n,k) × k)。

Pitfalls

常见误区

1. 把组合写成排列
若每层都从 1 开始选，[1,2] 和 [2,1] 会重复出现。组合必须保证 path 严格递增。
2. 收集结果时没有 copy path
ans 里存的是同一块切片引用，回溯 pop 后已收集答案会被改掉。
3. for 循环边界写错
上界应是 n-need+1，不是 n。写错会漏掉最后一个合法数字，或多做无效递归。
4. 不理解 start
start 不是装饰变量：它规定「只能向后选」，是去重的核心规则。
5. 复杂度误写成 O(n)
要输出 C(n,k) 个组合，每个复制 k 个数，时间是 O(C(n,k) × k)。