↩︎️ 回溯

在搜索空间中通过「选择 → 递归 → 撤销」的模板枚举所有可能性，适合排列、组合、子集、迷宫等问题。

8 题  ·  中等 ×7  困难 ×1

回溯模板

1
2
3
4
5
6
7
8

def backtrack(path, choices):
    if 满足结束条件:
        result.add(path.copy())
        return
    for choice in choices:
        做选择
        backtrack(path, remaining_choices)
        撤销选择

核心思路

• 全排列：used 数组记录已选，每次从未选中的数中选一个加入 path。
• 子集：从当前 index 开始枚举，每个节点都可以收录到结果集中。
• 组合总和：允许重复选，每次从当前 index 开始；剩余 target < 0 则剪枝。
• 括号生成：剩余左括号数 > 0 可加 (；剩余右括号数 > 剩余左括号数可加 )。
• N 皇后：用三个集合分别记录已占用的列、左对角线、右对角线，逐行放置皇后。