回溯算法

回溯算法三步走：

  1. 确定回溯函数的返回类型与函数参数（需要处理的参数）
  2. 确定回溯函数终止条件
  3. 确定单层搜索的过程

回溯完成之后，可以考虑剪枝。剪枝的意思是，for循环当中，集合从哪开始时可能满足条件，从哪开始不可能满足条件，把不可能的部分直接省略掉。

77. 组合 中等
216. 组合总和 III 中等
17. 电话号码的字母组合 中等

  1. 组合

    回溯法：组合问题，用回溯法三步骤来分析题目。记住，横坐标是遍历的范围，纵坐标的递归的次数。剪枝也是确定满足条件的情况下，这个范围不可能在哪里，于是就可以剪枝。可以这么理解，循环<=的那个数，是下一层循环开始的数，那么这个数至多是多少，算下来就可以达到剪枝的效果。

  2. 组合总和 III

    回溯法：组合问题，回溯法三步骤分析题目。关于剪枝：其实条件有3个，一个是从1到9里面取，第二个是结果=n，那么>n就没有必要继续遍历了，第三个是已经有一个数的情况下，我最多从第几个开始取9 - (k - path.size()) + 1

  3. 电话号码的字母组合

    回溯法：组合问题，回溯法三步骤分析题目。重点：用N叉树来建模问题。在这个问题里，宽度是第一个数字所对应字母的长度，而深度是digits的长度。将回溯法抽象为树形结构之后，其遍历过程就是：for循环横向遍历，递归纵向遍历，回溯不断调整结果集。