回溯算法

CHOOSE · CONSTRAINT · BACKTRACK

回溯核心

1. 选择

在当前状态做一次决策（选哪个元素、放哪一列等），进入新状态。

2. 约束

检查是否满足条件；不满足则剪枝，不再往下搜。

3. 回溯

递归返回时撤销本次选择，恢复状态，尝试其他分支。

全排列

生成数组的所有排列。每次从未使用元素中选一个加入当前路径，递归；返回时回溯（撤销选择），再试下一个。 

permute(path, remaining):
    if remaining 为空: 输出 path，return
    for each x in remaining:
        将 x 加入 path，从 remaining 移除
        permute(path, remaining)
        回溯：path 弹出，x 放回 remaining
当前路径：
剩余可选：