什么是回溯法？

Question

什么是回溯法？

Accepted Answer

**回溯法**逐步构建候选解决方案，一旦部分候选无法导向有效解决方案，就立即**放弃**该候选（回溯）。它通过 DFS 系统地探索解空间，修剪死路。

## 思想

选择 -> 探索 -> 撤销选择。尝试一个选项，递归；如果失败，撤销并尝试下一个。

## 示例：所有排列

```python
def permutations(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:              # complete solution
            result.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])              # choose
            backtrack(path, remaining[:i] + remaining[i+1:])  # explore
            path.pop()                             # un-choose (backtrack)
    backtrack([], nums)
    return result

permutations([1, 2, 3])   # -> 6 permutations
```

## 经典问题

- **N皇后问题**、数独、骑士巡游。
- **子集 / 组合 / 排列。**
- **单词搜索**、迷宫求解。

## 复杂度

通常是指数级（例如排列的 O(n!)），但**修剪**大幅减少实际搜索。

## 何时使用 / 陷阱

用于约束满足和