Leetcdoe刷题java之回溯法小总结

桃扇骨 2023-07-03 12:08 13阅读 0赞

刚开始的时候感觉回溯法很难，但是慢慢做下来，都是一个套路，并不是特别难。

回溯法，简单来说就是遍历所有排列组合，到头了再退回来。

先给一个回溯法框架，以及一道题来感觉一下：

[https://blog.csdn.net/qq\_41901915/article/details/104113330][https_blog.csdn.net_qq_41901915_article_details_104113330]

主要的几个需要注意的点就是：

第一个选择列表，也就是题目可选取的东西。

第二个就是track，路径，有时候这个路径是一个LinkedList，可以利用它的add和rermoveLast方法实现回溯。有时候这个路径是一个 StringBuilder，可以利用它的append和deleteCharAt（选择列表的长度减一）

第三个就是结束条件，也就是我们需要的结果，其实这个地方可以合并到去重当中。

第四个就是去重，也是不同题变种的最重要的一部分。

首先回溯法遍历的是所有的排列组合，根据不同的题目，我们需要去除掉一些重复的东西，就可以得到我们的结果。

1.第一种去重方法，利用track的大小，有时候题目要求的就是3个的排列组合，那么达到三个我们就可以得到结果

参考：[https://blog.csdn.net/qq\_41901915/article/details/104114605][https_blog.csdn.net_qq_41901915_article_details_104114605]

2.第二种去重方法，利用加入一个start索引来去重，每次递归方法都传入一个start索引，然后每次都从start开始循环，那么后面选择的就必须是大于前面索引的。

参考：[https://blog.csdn.net/qq\_41901915/article/details/104194993][https_blog.csdn.net_qq_41901915_article_details_104194993]

3.第三种去重方法，利用选过去重，可以创建一个visit，如果访问过了，将其制定为true。

参考：[https://blog.csdn.net/qq\_41901915/article/details/104131448][https_blog.csdn.net_qq_41901915_article_details_104131448]

参考：[https://blog.csdn.net/qq\_41901915/article/details/90698023][https_blog.csdn.net_qq_41901915_article_details_90698023]

4.第四种去重方法，对含有重复的进行去重，这个比较难理解，慢慢啃，说的就是选择空间里有重复的，比如AAB

参考：[https://blog.csdn.net/qq\_41901915/article/details/104153804][https_blog.csdn.net_qq_41901915_article_details_104153804]

这就是回溯法，我的博客中的回溯法分类还有类似的题，可供参考

[https://blog.csdn.net/qq\_41901915/category\_9688738.html][https_blog.csdn.net_qq_41901915_category_9688738.html]

[https_blog.csdn.net_qq_41901915_article_details_104113330]: https://blog.csdn.net/qq_41901915/article/details/104113330
[https_blog.csdn.net_qq_41901915_article_details_104114605]: https://blog.csdn.net/qq_41901915/article/details/104114605
[https_blog.csdn.net_qq_41901915_article_details_104194993]: https://blog.csdn.net/qq_41901915/article/details/104194993
[https_blog.csdn.net_qq_41901915_article_details_104131448]: https://blog.csdn.net/qq_41901915/article/details/104131448
[https_blog.csdn.net_qq_41901915_article_details_90698023]: https://blog.csdn.net/qq_41901915/article/details/90698023
[https_blog.csdn.net_qq_41901915_article_details_104153804]: https://blog.csdn.net/qq_41901915/article/details/104153804
[https_blog.csdn.net_qq_41901915_category_9688738.html]: https://blog.csdn.net/qq_41901915/category_9688738.html