稀有猿诉

十年磨一剑,历炼出锋芒,说话千百句,不如码二行。

回溯算法从入门到精通

回溯(Backtracking)是指在求解的过程中,不断的试探每一步的所有可能的解,如果发现不符合要求,就回退到最初的状态,尝试另外一种可能,直到所有的可能的解都找到。它与DFS的思想是一致的。

回溯通常用来解决的问题是,问题会分成很多步骤,每一步面临多个选择,有多种可能性,需要一个一个的尝试,最终需要找到所有的可能的解。回溯通常用递归来实现,并且它的时间复杂度一般都比较高。它基本上就是穷举和暴力搜索一样,但通过各种奇技淫巧可以做剪枝以降低复杂度。

最为经典的回溯算法问题就是迷宫问题,比如从一个格子a,出发,有二个方向,还不知道哪个是对的,那就分别向前走,一直走,直到撞墙了,或者到了死路了,才知道这个方向是错的;然后回退到a,按个方向继续走,这就是经典的回溯。

穷举问题

穷举,也就是穷尽所有的可能性,最为代表性的问题就是组合排列问题,这是回溯的典型问题。

题目 题解 说明
46. 全排列 题解
77. 组合 题解
784. 字母大小写全排列 题解
78. 子集 题解
题解
题解
题解

参考资料

Comments