题目描述
思路解析动画文字版
k=2 写两层 for,k=5 写五层……k 是变量时,嵌套循环根本写不出来。
转折:用递归代替「不定层循环」。每选一个数就从它后面继续选(start 保证只往后、天然去重,[1,2] 不会再冒出 [2,1]);选够 k 个就收进结果,然后撤销刚才那一步(path.pop)回到上层,换下一个候选。选→递归→撤销,三步循环。
选 1 · path=[1]:先选 1,path=[1]。接下来 start=2,只能从 2 往后挑,1 不再回头看。还没够 k=2 个,继续往下选。
选 2 · 凑够 2 个 → 收:再选 2,path=[1,2],长度到 k=2,收进结果 [1,2]。这条分支到头了,该回退。
撤销 2 · path=[1](回溯):负例/回溯动作:把刚选的 2 弹出,path 退回 [1],2 重新变回「可选」。不撤销的话 path 会越积越长、污染后面的分支。回到上层接着试下一个候选。
选 3 · 收 [1,3]:在 [1] 基础上改选 3,path=[1,3],够 2 个,收下 [1,3]。再撤销 3、改选 4……
选 4 · 收 [1,4]:同理收下 [1,4]。1 后面 2、3、4 都配过了,1 打头的组合全齐。接着把 1 也撤销,换头。
换头 · 2 打头 → [2,3]:回到最外层,改用 2 打头(start=3),收 [2,3]。注意 1 已撤销、不在 path 里——start 保证不会再回头配到 1。
2 打头 · 再收 [2,4]:撤销 3、改选 4,收 [2,4]。2 打头的也配完了,再撤销 2 换成 3 打头。
3 打头 · 收齐全部 6 个:3 打头收下 [3,4]。(4 打头后面没数了,凑不齐 2 个,是条死分支,直接返回。)最终 6 个组合全部收齐。
组合类题的核心——用 start 下标避免重复,让不定层数的枚举变成一个干净的递归。
参考代码
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复杂度
- 时间复杂度:O(C(n,k) · k),收每个组合要 O(k)
- 空间复杂度:O(k),递归深度 k
可套用的代码模板
骨架记牢:for 从 start 起、递归传 i+1(不是 start+1)、选完 pop。这是所有「组合 / 子集」题的母模板。
Python
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()易错点
这道题到这就讲完了。动画和文字是同一套思路——别光看,关掉页面自己默写一遍。然后顺着主线继续:
子集
LeetCode 78 · 中等 · 沿着 回溯套路 继续往下推进
把这道题真正学会,再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解(全站陆续覆盖)
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告,记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法,几十万开发者在看的算法讲解
想成体系刷透这类套路?去图解算法专题