面试必备：回溯算法详解

2024-07-15 17:49| 来源: 网络整理| 查看: 265

前言

大家好，我是捡田螺的小男孩。

我们刷leetcode的时候，经常会遇到回溯算法类型题目。回溯算法是五大基本算法之一，一般大厂也喜欢问。今天跟大家一起来学习回溯算法的套路，文章如果有不正确的地方，欢迎大家指出哈，感谢感谢~

什么是回溯算法？一道算法题走进回溯算法回溯算法框架套路leetcode案例分析1. 什么是回溯算法

回溯算法，一种通过探索所有可能的候选解来找出所有的解的算法。

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

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

举个类似的生活例子，比如放羊娃的羊在分岔路口走丟了，他顺着不同的岔路口寻找羊，一个岔路口一个岔路口的去尝试找羊。如果找不到羊，继续返回来找到岔路口的另一条路，直到找到羊为止。

如下图为找羊的决策路线图：

放羊娃在A方向找，然后走C方向，没找到时，他回到分岔路，又朝D方向走...直到找到羊，这就是回溯。

2. 一道算法题走进回溯算法

给定一个不含重复数字的数组 nums ，返回其所有可能的全排列。你可以按任意顺序返回答案。

示例 1：

代码语言：javascript复制输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

实例2：

代码语言：javascript复制输入：nums = [0,1] 输出：[[0,1],[1,0]] 2.1 实现思路

看完这道题，我们的第一想法就是穷举全排列呀，但是你不会毫无规律得穷举对吧。比如要排3个数[1,2,3],你会第一位先排1，然后第二位只能是2或者3，如果第二位是2，第三位只能是3了...

我们可以借鉴羊娃找羊的路线图，画出全排列的树图，如下：

其实我们是不是从根节点遍历这棵树，记录下走过路径的数字，走到叶子节点，就可以得到一个排列啦。走完所有的叶子节点，那就可以得到全排列啦。

这棵树的如何理解更清晰呢？

为了方便理解，我们可以把nums个数k看做k种选择，比如对于[1,2,3]，每一位都有3种选择：1、2、3。每一次做选择，都展开出一棵空间树，选择完后，如果是重复选的路径，就做剪枝。

上图的那颗树，可以看做是遍历所有元素，展开空间树，然后剪枝得来的。如下图

好啦，现在知道树怎么来的，我们来看下怎么遍历找到全排列呢？每次走树的分支，都像是在做决策。我们可以把已走的路径和可做的选择作为树节点的两个属性。

如果在根节点，可做的选择为1、2、3，走过的路径为空，如下图

走到叶子节点时，已走路径数组长度等于原素组的个数，这时候走过路径就是满足条件的一个解。

2.2 代码实现

代码怎么写呢？以前我们学习树的遍历，一般都用到递归，这道题也用递归。

递归入口是什么呢？一个可选路径和已走过的路径就好啦。递归函数体呢？一个for循环，枚举当前数组的元素，并且需要if判断，以跳过剪枝递归出口呢？也就是走到叶子节点啦，叶子节点，就是当构建的已走路径path的数组长度等于nums的长度

实现代码如下：

代码语言：javascript复制 class Solution { //全排列，即所有路径集合 List allPath = new LinkedList(); public List permute(int[] nums) { //当前路径，入口路径，path是空的 List path = new LinkedList(); //递归函数入口，可做选择是nums数组 backTrace(nums,path); return allPath; } public void backTrace(int[] nums,List path){ //已走路径path的数组长度等于nums的长度,表示走到叶子节点，所以加到全排列集合 if(nums.length==path.size()){ allPath.add(new LinkedList(path)); return; } for(int i=0;i= candidates[i]) { //做选择 path.add(candidates[i]); //递归 backTrace(candidates, target - candidates[i], path, i); //撤销选择 path.remove(path.size() - 1); } } } } 参考与感谢《labuladong的算法小抄》leetcode官网

【本文地址】

公司简介

联系我们