回溯算法

尝试所有可能选择 → 不可行时回退 → 通过剪枝避免无效搜索。本质是 DFS 的试错形态。

通用框架

def backtrack(state, choices, res):
    if is_solution(state):
        record(state)        # 记录解
        return
    for choice in choices:
        if is_valid(state, choice):   # 剪枝
            make_choice(state, choice) # 尝试
            backtrack(state, choices, res)
            undo_choice(state, choice) # 回退

关键机制

• 剪枝：提前排除不可能产生解的路径，大幅减少搜索空间
• 状态恢复：回退时必须撤销当前选择，保证上层共享的 state 状态正确

典型问题

全排列、子集和、n 皇后、数独求解、组合总和。