以回溯算法的经典题目作为一个备忘。
主要参考:
代码随想录 Leetcode
目录
回溯算法是什么?
采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:
找到一个可能存在的正确的答案;
在尝试了所有可能的分步方法后宣告该问题没有答案。
回溯法,⼀般可以解决如下⼏种问题:
组合问题:N个数⾥⾯按⼀定规则找出k个数的集合
切割问题:⼀个字符串按⼀定规则有⼏种切割⽅式
⼦集问题:⼀个N个数的集合⾥有多少符合条件的⼦集
排列问题:N个数按⼀定规则全排列,有⼏种排列⽅式
切割问题:⼀个字符串按⼀定规则有⼏种切割⽅式
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/92854.html