• 代码模板

  • 跳出递归的终止条件
  • 处理当前层的逻辑
  • 跳入至下一层
  • 清理当前层状态

• 注意事项

  • 避免人肉递归
  • 找最小重复子问题
  • 数学归纳法： 即证明n , n+1满足某种规律。

分治简单说就是将一个问题分成多个相同逻辑子问题，最后对子问题的返回结果聚合处理，得到最终结果。

比如求n的k次幂，就可以把问题转化为求n的k/2次幂，这样相对于暴力循环来说就可以减少重复的计算步骤。

回溯从代码的逻辑上讲就是通过一步步尝试来判断是否满足预期结果（列出所有可能性）的求解方式。在编码时需要注意的是: 一般来说在代码末尾需要回溯，即清除当前层操作留下的痕迹(删除在当前层插入到列表中的元素)。

常用于求组合的所有可能性。 比如求一个数组中的所有数组合的子集。

分治和回溯本质上也是一种递归，只是在计算逻辑细节上有一些差别，分别用来解决特定场景的问题。