一、回溯算法理解
本质是以深度遍历的方式遍历决策树
但因为没有具体的TreeNode构成树，所以回溯与DFS遍历树很像，但不同的是回溯要多一步退回选择的操作
典型问题:全排列、N皇后问题
回溯算法的构成要素:
①选择列表
②已选路径或已做出的选择(trace或used)
③结束条件
回溯算法的模板如下:
def backTrace(已选路径, 选择列表) {
if(结束条件) {
return ; // 对于return 如果只问是否有解则返回bool即可;如果要所有的解则用全局变量数组保存所有找到的解
}
for 某选择:选择列表 {
if(不必要选择) {
continue;
}
做选择:某选择加入已选路径，下一步选择列表是否变化
backTrace(已选路径, 选择列表)
回退选择:某选择退出已选路径，回退后选择列表是否需要恢复
}
}
回溯算法的思路如下:
画决策树，决策树节点的属性就是 选择和当前路径 我们的backTrace函数在树的各个节点游走，知道遇到结束条件
