第7章｜回溯与搜索
Unit 02 · LeetCode #77 · 优化版
← Unit 01
77
CombinationsFixed Depth · Capacity Pruning
只记录填满 K 个位置的状态，
提前拒绝永远填不满的选择。
path 与 start 延续子集模型；组合题新增固定深度与容量约束。真正值得掌握的不是公式本身，而是它证明了哪些候选已经不可能完成。
题目要求
给定两个整数 n 和 k，返回范围 [1,n] 中所有可能的 k 个数的组合。组合不考虑顺序，答案顺序任意。
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
pass
- 只有长度恰好为
k的路径是答案； - 下一层从
value+1开始，保证严格递增； - 答案数量为
C(n,k)。
教学实验
n = 5, k = 3
完整答案示例：[1,3,5]
中间状态示例：[1,3]
need = k - len(path)
max_value = n - need + 1
range 的排他终点 = max_value + 1
主方法仍为回溯，但本页只训练三个新增点：固定记录时机、容量剪枝的证明，以及 Python 排他边界。
固定深度只有
len(path)==k 才记录，较短路径只是中间状态。need还缺多少个位置：
k-len(path)。最大候选
n-need+1 是本层最后一个仍可能完成的选择。排他终点Python
range 不包含右端，因此代码写 max_value+1。检测到本单元进度
教学搜索树｜n=5，k=3
绿色底线：完整组合橙色：当前状态黄色：可操作候选红色：容量不足
组合搜索契约
当前 start
还缺 need
本层最大候选
已记录答案数
当前候选窗口
补全 LeetCode #77 提交代码7 个语义槽位
代码—need—候选上界联动在排他边界处暂停
代码槽位与关键轨迹都完成后，本环节结束槽位表达算法契约；轨迹验证排他边界和状态恢复。
Unit 02 Skill 总结
状态path、start、need
答案条件len(path)==k
容量剪枝max=n-need+1
Python 边界range(start,max+1)
唯一性下一层 value+1
迁移#216 再增加 remaining