回溯

写此系列博客的榜样来自：leetcode cookbook

套路

增量构建答案的过程，通常由递归实现

回溯三问：

1. 当前操作？枚举path[i]要填入的字母
2. 子问题？
3. 下一个子问题

先写二叉树回溯,再做的通用回溯。二叉树型回溯和多叉树(通用型)回溯的区别就是 通用型要写for loop，而二叉树只有2个选择，所以没有for loop，直接执行dfs(node.left)和dfs(node.right).

从写代码的角度对比,几乎完全一样:

确定递归函数的意义：

1.1 def dfs(node):从上到下遍历树的每一个node
1.2 def dfs(i):从index 0开始构造这条路径

确定base case：

2.1 if node is None 所有该遍历的节点已经遍历完了(node是叶子节点的时候，就是最后一片要遍历的叶子）
2.2 if i == n 这条路径已经被填满了(i=n-1的时候，就是最后要处理的一个path格子)

确定单层递归的当前操作:

3.1 加入pathpath.append(str(node.val)) 且 进行下层递归dfs(node.left) dfs(node.right) 且恢复现场path.pop()
3.2 在for loop下加入path在for loop下: path.append(c) 且 进行下一层递归dfs(i + 1) 且恢复现场path.pop

子集型回溯

1. 当前操作？
2. 子问题？
3. 下一个子问题

组合型

排列型