LeetCode 77中等回溯 · 组合
组合 图解题解
这道题到底在问什么
给定 n 和 k，返回 1..n 中所有 k 个数的组合。
- 输入
- n=4, k=2
- 输出
- [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]] 共 6 个
最优解：一步一步想明白
- 3思路一句话：从 start 往后选（升序去重），凑够 k 个就收集，剩数不够补满就剪枝。下面一步步演给你看。
- 4选数字 1（下标 0）。还需选 1 个，下一层只能从它右边（下标 1）继续，这样组合天然升序、不会重复。
- 5选数字 2（下标 1）。还需选 0 个，下一层只能从它右边（下标 2）继续，这样组合天然升序、不会重复。
- 6path 已凑满 2 个 → 收集组合 [1, 2]。这是第 1 个答案。
- 7回退：撤销 2，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 8选数字 3（下标 2）。还需选 0 个，下一层只能从它右边（下标 3）继续，这样组合天然升序、不会重复。
- 9path 已凑满 2 个 → 收集组合 [1, 3]。这是第 2 个答案。
- 10回退：撤销 3，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 11选数字 4（下标 3）。还需选 0 个，下一层只能从它右边（下标 4）继续，这样组合天然升序、不会重复。
- 12path 已凑满 2 个 → 收集组合 [1, 4]。这是第 3 个答案。
- 13回退：撤销 4，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 14回退：撤销 1，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 15选数字 2（下标 1）。还需选 1 个，下一层只能从它右边（下标 2）继续，这样组合天然升序、不会重复。
- 16选数字 3（下标 2）。还需选 0 个，下一层只能从它右边（下标 3）继续，这样组合天然升序、不会重复。
- 17path 已凑满 2 个 → 收集组合 [2, 3]。这是第 4 个答案。
- 18回退：撤销 3，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 19选数字 4（下标 3）。还需选 0 个，下一层只能从它右边（下标 4）继续，这样组合天然升序、不会重复。
- 20path 已凑满 2 个 → 收集组合 [2, 4]。这是第 5 个答案。
- 21回退：撤销 4，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 22回退：撤销 2，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 23选数字 3（下标 2）。还需选 1 个，下一层只能从它右边（下标 3）继续，这样组合天然升序、不会重复。
- 24选数字 4（下标 3）。还需选 0 个，下一层只能从它右边（下标 4）继续，这样组合天然升序、不会重复。
- 25path 已凑满 2 个 → 收集组合 [3, 4]。这是第 6 个答案。
- 26回退：撤销 4，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 27回退：撤销 3，把它从 path 拿掉，换右边的数再试（这就是「回溯」——试完一条路就退回来换下一条）。
- 28剪枝 ✗：还需 2 个，但从下标 3 往后只剩 1 个，凑不满了，直接砍掉这一支，省去无用搜索。
- 29搜索结束：共找到 6 个组合。回溯就是「选一个→往深搜→退回来换下一个」，配合 start 升序和剪枝，不重不漏。
⚠️ 容易写错的地方
✗ 错：下一层还从 0/1 开始选
✓ 对：下一层从 i+1 开始
否则会选出 {2,1} 这种重复组合
✗ 错：不剪枝，全枚举到底
✓ 对：剩余不够 k 就提前返回
大量死支白搜，超时
✗ 错：收集时直接存 path 引用
✓ 对：存 path 的拷贝
path 会被后续回溯改掉，引用会全变样
完整代码（Python / C++ / Java）
Python
def combine(n, k):
res, path = [], []
def bt(start):
if len(path) == k:
res.append(path[:]); return
# 剪枝：剩余不够补满 k 个就停
for i in range(start, n - (k - len(path)) + 2):
path.append(i)
bt(i + 1)
path.pop()
bt(1)
return resC++
vector<vector<int>> res; vector<int> path; int N, K;
void bt(int start){
if((int)path.size() == K){ res.push_back(path); return; }
// 剪枝：i 太大、剩余补不满就停
for(int i = start; i <= N - (K - (int)path.size()) + 1; i++){
path.push_back(i);
bt(i + 1);
path.pop_back();
}
}Java
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> path = new ArrayDeque<>();
int N, K;
void bt(int start){
if(path.size() == K){ res.add(new ArrayList<>(path)); return; }
// 剪枝：剩余不够补满 K 个就停
for(int i = start; i <= N - (K - path.size()) + 1; i++){
path.addLast(i);
bt(i + 1);
path.removeLast();
}
}复杂度
时间
O(C(n,k)·k)
共 C(n,k) 个组合，每个拷贝 k 个数
空间
O(k)
递归深度 + path 长度都是 k
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 组合 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
组合和排列回溯的区别？+
组合用 start 限定「只往后选」（不看顺序）；排列用 used 数组标记并从头扫（看顺序）。
剪枝的上界怎么推的？+
还需选 need=k-path.size() 个，最后一个 i 最大只能是 n-need+1，再大右边就补不满 need 个。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 组合 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
把这道题真正拿下
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。