代码随想录第二十二天刷题

class Solution:
    def combine(self, n: int, k: int) -> List[List[int]]:
        result = []
        self.backtracking(n, k, 1, [], result)
        return result
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])
            return
        for i in range(startIndex, n+1):
            path.append(i)
            self.backtracking(n, k, i + 1, path, result)
            path.pop()
# ---------- 回溯模板 ----------
# 1. 终止条件：len(path) == k
# 2. for 循环：从 startIndex 开始
# 3. 做选择 → 递归 → 撤销选择
#
# path.pop() 是回溯的灵魂
# 保证状态可复用

#        self.backtracking(n, k, 1, [], result)
# ---------- 回溯参数理解 ----------
# self.backtracking(...)
# self. 是因为这是类的方法
#
# [] 表示：
# 当前路径 path 的初始状态
#
# result 是：
# 所有合法路径的最终集合
#
# path ≠ result

# ---------- 回溯中的拷贝 ----------
# result.append(path)   ❌
# result.append(path[:]) ✅
#
# 原因：
# path 是可变对象
# 回溯会不断修改它
# 必须保存“当时状态的副本”
#
# path[:] == 列表切片拷贝

# ---------- 回溯剪枝 ----------
# for i in range(startIndex, 9 - (k - len(path)) + 2):
#
# 含义：
# 1. startIndex：去重
# 2. 上界：保证后面还有足够数字可选
#
# Python range 特点：
# range(a, b) 不含 b
# 所以要 +1


# ---------- 回溯剪枝：上界计算 ----------
# 1. 还需要数字：
#    need = k - len(path)
#
# 2. 理论上界：
#    max_i = 9 - need + 1
#
# 3. Python range 不含 end：
#    range(start, max_i + 1)
#
# 4. 合并后：
#    range(startIndex, 9 - need + 2)

# ---------- 回溯中的 path ----------
# path = 当前的一条路径（一个组合）
# result = 所有合法路径的集合
#
# len(path)：
# 表示当前路径已经选了多少个数
#
# 不要混淆：
# path ≠ result

# ---------- 回溯参数设计 ----------
# 回溯函数 = 状态机
#
# 常见参数：
# 1. 目标值（不变）
# 2. 限制条件（k）
# 3. 当前状态（currentSum）
# 4. 起始位置（startIndex / i+1）
# 5. 当前路径（path）
# 6. 结果集（result）
# ---------- 回溯参数顺序 ----------
# 1. 语法上：参数顺序可以改
# 2. 逻辑上：状态参数必须对应
# 3. 推荐顺序（不易出错）：
#    目标值 → 限制 → 当前状态 → startIndex → path → result

# ---------- Python 构造函数 ----------
# ✅ 正确：
# def __init__(self):
#
# ❌ 常见错误：
# def _init_(self):
# def __int__(self):
#
# __init__：
# 1. 创建对象时自动执行
# 2. 用来初始化 self.xxx