回溯内容部分总结

2020 09 20 学回溯有感

回溯是什么

回溯是一种技巧，用于用于数据排列的方式的技巧，同时也是另一种形式的枚举。其原理是对数据的处理结果如同对一个数字加上1和减1，最终得出的结果是不变的。我称之为可再现性。尤其是在计算机中可以对原有的数据轻松地更改和恢复，所以才会广泛应用。

所以回溯的核心原理就是通过部分数据进行增加或者删除之后的，得到其中一部分的结果后进行相反操作如删除和增加，从而恢复现场。同样在此过程可以进行递归，所以一般回溯都会与递归，深度优先连接在一起。最终将所有的部分的结果进行整合成最终结果。

回溯一般包括剪枝，也就是对不符合条件的内容设立条件进行筛选，优化得到最终结果的性能。这是在过程中筛选出合适的部分结果

也可以在得到结果之后再进行设立条件进行排除不合适的答案，这样性能会比较差。

详细要点

• // 大致模板
  
  res.add(new ArrayList<>(tmp));
  
  if( xxx ){
      tmp.add();  // 增加
      backstrack(); //下一步地迭代回溯
      tmp.remove(); //还原
  }
  

• 回溯的过程 尤其是需要注意边界。还有递归的终止条件

• 去重的时候可以采用获取所有结果后利用HashMap的方式进行去重，

Leetcode题目

• 子集
• 全排列
• 组合总和

三种类型题各有不同。其中子集的是没有进行规定子数组的大小的，全排列要求的数组是个数是整齐的，组合总和的是能够凑成总和的个数。具体详情可以观看我的解题过程