# Summary
回溯是种写起来简洁的多层for*暴力穷举*搜索，再配合一些剪枝优化。
为啥能写起来简洁，因为用了递归
对于要穷举的树结构，backtrack函数是纵向逻辑，for循环是横向逻辑，最终实现对树结构的穷举
```java
void backtracking(参数) {
// 终止条件
if () {
存放结果;
return;
}
// 处理逻辑
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
```
# Cues
# Notes
| Category | Sub-category | Topic | Related Topic | Notes |
|:------------------ |:---------------- |:------------------- |:---------------------- |:------------------------------------------------------------------------- |
| **回溯 backtracking** | **二叉树回溯** | 15. 二叉树递归中带着回溯 | | |
| | | 13. 二叉树的所有路径 | | |
| | | 18. 路径总和 | JZ82 二叉树中和为某一值的路径(一) | 左右孩子都为空的节点才是叶子节点 |
| | | 113. 路径总和 II | JZ84 二叉树中和为某一值的路径(三) | |
| | | JZ34 二叉树中和为某一值的路径(二) | | |
| | | 27. 二叉树的最近公共祖先 | JZ86 在二叉树中找到两个节点的最近公共祖先 | |
| | | 22. 括号生成 | | |
| | **多层for回溯** | 2. 组合问题 | | |
| | **各种path不等长，重结果** | 7. 组合总和 | 无重复元素的整数数组 | |
| | | 8. 组合总和II | 有重复元素的整数数组 | res里面加path需要深拷贝, res.add(new ArrayList(path))不然只是引用的话, res里的内容会随着path变化而变化 |
| | | 4. 组合总和III | | |
| | | 21. 组合总和Ⅳ | 无限背包 | 组合问题上回溯和背包的区别 |
| | | 11. 子集问题 | | |
| | | 13. 子集II | | 树层去重 |
| | **各种path等长，重方式** | 5. 电话号码的字母组合 | | |
| | | 15. 全排列 | | used数组 |
| | | 16. 全排列II | JZ38 字符串的排列 | 排序+used数组 |
| | | JZ12 矩阵中的路径 | | 深入理解 dfs/深度优先/递归 + 路径技巧 |
| | | 9. 分割回文串 | | |
| | | 10. 复原IP地址 | | |
| | | 12. 回溯周末总结 | | |
| | | 14. 递增子序列 | | |
| | | 17. 回溯周末总结 | | |
| | | 18. 回溯算法去重问题的另一种写法 | | |
| | | 19. 重新安排行程 | | |
| | | 20. N皇后 | | |
| | | 21. 解数独 | | |
| | **图回溯** | 797. 所有可能的路径 | | |
| | | 22. 回溯法总结篇 | | |