回溯法

类似枚举，一层一层向下递归，尝试搜索答案

• 找到答案 -> 尝试别的可能 -> 返回答案
• 找不到答案 -> 返回上一层递归，尝试别的路径

引例 LeetCode 78.子集

给定数组[1, 2, 3]，子集长度0, 1, 2, 3

返回数组所有可能的子集

• 手写所有结果：

子集长度	子集
0	[]
1	[1], [2], [3]
2	[1, 2], [1, 3], [2, 3]
3	[1, 2, 3]

要求找到所有可能的子集，而回溯具有枚举性

• 开始找长度为1的，先找到[1]，满足了条件，没必要往下走了，故回溯，找到了[2]，再回溯，找到[3]再回溯
• 开始找长度为2的，先找到[1]，发现长度不对，就向下递归，找到了[1, 2]，回溯，找到[1, 3]回溯，找到[2]发现长度不对，递归，找到[2, 3]回溯，找到[3]发现长度不对，递归，发现没东西了
• 开始找长度为3，找到[1]发现长度不对，递归找到[1, 2]不对，递归，找到[1, 2, 3]满足条件回溯到[1, 2]发现后面没东西了，回溯找到[1, 3]发现长度不对故递归，发现没东西，回溯找到[2]，发现长度不对，递归找到[2, 3]发现长度不对，递归，发现没东西了，回溯找到[3]发现长度不对，递归，发现后面没有元素了
• 结束，输出整个结果集

---

leetcode题目

• 22.括号生成
• 78.子集
• 77.组合
• 46.全排列

经典回溯难题

• 八皇后问题
• 数独