LeetCode上几道经典的回溯法题目

把相同类型的题目放在一起总结,可以便于整理思路,理解异同。下面是LeetCode上几道比较经典的可以使用回溯法来解决的题目,也是笔试面试时常考常问的。

在找实习时我就被问了两次Subsets这道题。因此熟练掌握这几道题,面试时遇到类似的题目即使是不能一下子写出正确的代码,至少也能按照正确的思路去思考。

回溯法

维基百科上回溯法的定义:

回溯法(英语:backtracking)是暴力搜寻法中的一种。

对于某些计算问题而言,回溯法是一种可以找出所有(或一部分)解的一般性算法,尤其适用于约束满足问题(在解决约束满足问题时,我们逐步构造更多的候选解,并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解,转而测试其他的部分候选解)。

回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况:

  • 找到一个可能存在的正确的答案
  • 在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下,回溯法会导致一次复杂度指数时间的计算。

将问题的初始状态看作是一个树的根部,针对初始状态,可能有很多可能的解法,每个解法对应树的一个分岔,使用该解法得到的新的问题状态对应根结点的孩子结点。对每个新的问题状态,又有很多可能的解,所以会继续形成分叉,生成新的问题状态(子结点)。

依次递归下去,直到问题的一个状态不存在任何可能的解法时,将此状态记为叶子结点,同时标记为“不可达”。当问题的一个状态就是初始问题的一个解法时,也将其记为叶子结点,同时标记为“可行解”(可能有多个可行解)。所以,树的中间结点代表了所求解问题的一个中间状态,叶子结点代表找到了问题的解或者达到绝境。这里抽象出来的树一般称为解空间状态树。根据上述基本思想,我们可以给出一个回溯法解决问题时的基本模板:

Subsets

题意

给定一个元素各不相同的数组,求出这个数组中元素能够组成的所有集合。如给定[1,2,3],那么集合共有8个,分别是[[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]

实现

 

Combinations

题意

给定两个整数n和k,求出从n中取k个数的所有可能。如输入n=4,k=2,返回[[2,4],[3,4],[2,3],[1,2],[1,3],[1,4]]

实现

这一题可以看做是上一题的mini版,因为如果我们让k从0~nums.size()取值的话,就变成上一题了,所以实现也是类似的。

 

Combination Sum

题意

给定一组元素各不相同的数组和一个目标数,数组中存在一些数字的组合,使得这些数字的和等于目标数,找出这些数字组合的所有可能情况。如输入[2,3,6,7]和7,返回[[7],[2,2,3]]

实现

 

Permutation

题意

给定一组数字,求出这组数字的全排列。

实现

前面一篇博客中已经对全排列系列的问题进行了总结,因此在这里直接贴出代码,不再分析了。

 

Path Sum II

题意

给出一棵二叉树和一个目标数字,每个二叉树上的节点上面有个数字,找出所有从根节点到叶子节点的路径,使得路径上的节点数字之和为给定的目标数字。

实现

 

小结

总结了如上几道题,我们发现以上题目都有些共同特点:如果题目要求所有符合某一条件的集合,那么就可以考虑用回溯法来解决。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据