前言 ✨
作为转专业🥧的学生，加上大一下学期的疫情原因，在家上网课基本就是三天打🐟两天晒网的状态。一直挺抵触算法的(未知的恐惧感)。大二下学期接触前端之后到去年9月份之前也没有怎么刷过算法。一直都是使用JS作为第一语言去学习算法的，经过这一两个月的算法刷题之旅感觉收获也挺多的，可能是变得更加自信了，即便有些问题一时半会想不出题解，还是愿意每天沉下心来，安安静静的去欣赏(借鉴)一段代码，有些时候不得不感慨好的代码会和诗一样的优美,看完某些大神的题解也会有茅塞顿开的感觉。
解决一道适中难度的算法题就好比攀登一座高峰，往往它给我带来的满足感不仅仅于力扣上的解决问题+1。 这个过程就像绳锯木断一般，坚持下来收获的远比我们自己想象的多。✨
心得分享
首先自己也不是什么大神，分享这篇文章，是想帮助和我一样在学习算法的小白。前端学习路上基本上都是抱团取暖，学习和模仿本就是我们与生俱来的能力☑。笔者作为平台的受益者现在也将个人的一些经验分享给大家，希望能对你有所帮助。
本文的数据来源于 CodeTop企业题库
强调重点:
- 多画图
- 多画图
- 多画图 如何去面对自己不会的题目，直接看题解有些时候是比较难以理解的，将问题通过画图的方式✍下来，就会
让你做小学数学一般📕在其中寻找规律，这个习惯不仅仅适用于本文介绍的回溯算法。所以倔友哈皮😎一定要养成画图的习惯 !
（一）回溯解题思路 ✨
1.1 回溯算法介绍
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。 ---《百度百科》 回溯算法的本质就是一个暴力搜索的过程。
从一条路往前走，能进则进，不能进则退回来，换一条路再试。 不撞南墙不回头的算法
1.2 回溯算法主要解决的问题
- 组合问题：
N个数里面按一定规则找出k个数的集合 - 排列问题：
N个数按一定规则全排列，有几种排列方式 - 切割问题：
一个字符串按一定规则有几种切割方式 - 子集问题：
一个N个数的集合里有多少符合条件的子集 - 棋盘问题：
N皇后，解数独等等
1.3 回溯算法的模板
框架的意义是快速帮助我们搭建好解题的步骤，减少出现有思路但是不知道如何下手的情况。 回溯算法也有自己的一套框架。
- 回溯算法基本上都能看作一颗N叉树，横轴意味着选择元素的个数，纵轴是递归的过程。
function backtrak(参数){ if(递归终止条件){ // result.push() 添加结果集 return } for(元素 in 集合){ 做出选择 backtrack(当前的选择结果) 撤销选择 // 这一步就是回溯的操作 } }
(二)回溯算法示例
带入我们上述的解题框架之后，再通过画图的方式讲步骤呈现出来，回溯算法也就迎刃而解了。我们来看看几个示例吧。
2.1 全排列 力扣46.全排列
2.1.1 问题描述
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入： nums = [1,2,3] 输出： [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：
输入： nums = [0,1] 输出： [[0,1],[1,0]]
示例 3：
输入： nums = [1] 输出： [[1]]
2.1.2 问题分析
[1,2,3]的全排列问题就等于 1 + [2,3]的全排列、2 + [1,3]的全排列、3 + [1,2]的全排列
- 第一次选择我们可以选择 1，2，3 中的任意一个
仔细想一想是不是对应着上文所述的横轴for循环 - 第二次选择的时候，要避免选择我们第一次选择的元素
这个简单用一个map记录 - 选到第三个的时候，就可以出结果了
递归终止条件 - 撤销刚刚选的，看看还有没有其它可以选的，如果没有其它选择，继续撤销。 (这一步可能有点稍微抽象，等会见代码就好理解了)
我们刚在分析的过程从第一个选到第三个的过程，每次都携带了本次的选择结果，其实就是一个递归的过程。
图片来源: 笨猪爆破组
2.1.3答案
var permute = function(nums) { const res = [] // 存储所有结果 const map = {} // 记录当前元素是否存在 const dfs = (arr)=>{ if(arr.length==nums.length){ res.push(arr.slice()) // 对数组进行浅拷贝，避免后续操作数组会影响到res的值 return } for(const num of nums){ // 横向遍历 if(map[num]){ // 这个元素已经选过 continue } map[num] = true arr.push(num) // 选择元素 dfs(arr) // 递归 arr.pop() // 撤销选择 map[num] = false } } dfs([]) return res };
2.2 复原IP地址 力扣93.复原IP地址
2.2.1 问题描述
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
2.2.2 问题分析
横向for循环：我们每次最多选择几个？
- 根据题目要求来看，每次最多选择三个最少选择一个
- 每次选择大小只能在0~255之间
- 如果选择大于等于两位，则不能出现
0X0XX这样的情况 纵向递归：确定终止条件 - 已经选择了四次，但是ip地址还没选完
- 已选择的长度的个数超过了整个ip地址的长度 使用index值来记录ip字符串下标的方式进行选择
图片来源: 笨猪爆破组
回溯算法会穷举所有的节点，找出所有可能组合的结果。
2.2.3 答案
var restoreIpAddresses = function(s) { const res = [] // 结果集 // ipArr 存放每一个可能的ip地址，当其长度为4的时候进行递归终止条件判断 const dfs = (ipArr,index)=>{ if(ipArr.length==4){ if(index==s.length){// 最终选择完长度刚好等于ip字符串 满足条件，终止递归 res.push(ipArr.join('.')) } // 最终选择完，但是还没有完全选完或者长度超过了ip字符串长度，终止递归 return } // 还没选择完 for(let len=1;len<=3;len++){ // 每次选择1~3个 if(len!=1&&s[index]=='0') return // 选择2-3个元素的时候，不能以 ‘0’开头 const ipChild = s.substr(index,len) // 截取刚才我们选好的子ip地址 if(+ipChild>255) return // 范围限制 ipArr.push(ipChild) // 添加 dfs(ipArr,index+len) ipArr.pop() // 回溯（撤销添加） } } dfs([],0) return res };
2.3 组合总和 力扣39.组合总和
2.3.1 问题描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7 输出：[[2,2,3],[7]]
解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8 输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1 输出: []
2.3.2 问题分析
灵魂之问？ ： 这一题会选择使用回溯算法呢？
观察题目的共同特点，你会发现你每一次都可以做选择，选择的展开就是一个N叉树。当不符合条件的时候又无法直接重新开始，例如我在【1，2，3，4】中进行选择，选择了【1，2，3】之后发现3不满足条件，我需要回到【1，2】这个状态再去才重新选择。面对这种类似问题的时候，题目往往需要的是某一个结果集，而不是个数/最大最小这样的条件。集中性的练习会让你面对这类问题的时候很快想到回溯算法。
这一道题的解法比前面两道都要简单，而且约束条件也很清晰
横向for循环：
- 每次可以选择任意一个元素（可以重复选择） 纵向递归：
- 当选择的结果和大于等于目标值终止递归 但是还需要注意一点: 例如示例一，当满足
[2,2,3]的时候就无需输出[3,2,2]、[2,3,2]所以题目所求子集问题，而不是排序问题。
如何做到这一点呢？ 很简单，给一个元素的起始下标即可。
2.3.3 答案
var combinationSum = function(candidates, target) { const res = [] // 结果集 const dfs = (start,path,sum)=>{ if(sum>=target){ // 递归终止条件 if(sum===target){ res.push(path.slice()) } return } for(let i=start;i<candidates.length;i++){ path.push(candidates[i]) dfs(i,path,sum+candidates[i]) path.pop() // 回溯 } } dfs(0,[],0) return res }
2.4 括号生成 力扣22.括号生成
2.4.1 问题描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。 示例 1：
输入：n = 3 输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1 输出：["()"]
2.4.2 问题分析
这题可以使用栈来解决，这里就不演示了。我们还是使用动态规划的思路来做。
横向for循环:
- 每次我们
要么选左括号，要么选右括号纵向递归: - 递归终止条件，当前括号选择的长度等于目标值的两倍（一对括号对应n=1）
图片来源: 笨猪爆破组
2.4.3 答案
var generateParenthesis = function(n) { const res = [] // 结果集 // l表示左括号还剩可以选的数量，r右括号; str表示当前选的结果 const dfs = (l,r,str)=>{ if(str.length==n*2){ res.push(str) return } if(l>0){ // 左边括号只要还有剩余就可以选 dfs(l-1,r,str+'(') } if(r>l){ // 右边括号剩余数量大于左边剩余括号数量时可选 dfs(l,r-1,str+')') } } dfs(n,n,'') return res };
2.5 字符串的排列 脚趾offer38.字符串的排列
2.5.1 问题描述
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入： s = "abc" 输出：[ "abc","acb","bac","bca","cab","cba" ]
2.5.2 问题分析
如果仔细看完上面的四道题，拿到这道题就会马上想到回溯算法了。因为很明显就是一个N叉树展开就结果的过程。 横向for循环： 选择元素
- 第一次可以任意选元素，后面选择的元素必须是当前
选择路径没有出现的。 例如a->b之后不能再选择a或者b 纵向递归：确定递归的终止条件 - 传入一个num，记录路径的长度，长度等于目标长度的时候终止递归
2.5.3 答案
版本 1
var permutation = function(s) { const res = [] const used = {} const dfs = (num,path)=>{ if(num==s.length){ res.push(path.join('')) return } for(const c of s){ if(used[c]){ continue } used[c] = true path.push(c) dfs(num+1,path) used[c] = false path.pop() } } dfs(0,[]) return res };
版本1会和我们之前做过的全排列非常相似。但是当测试用例为 aac的时候就无法通过，那我们就不标记值，换一种思路，标记下标。
标记下标也会出现另一个问题，那就是重复： 同样的还是拿aac来举例子，下标 0,1,2 和 下标1,0,2是一样的。所以我们还需要对结果进行一个去重操作。
var permutation = function(s) { const res = [] // 结果集 const used = [] // 记录选择路径下标 const dfs = (path)=>{ if(path.length==s.length){ // 递归终止条件 res.push(path) return } for(let i=0;i<s.length;i++){ if(used[i]) continue used[i] = true // 这里直接将path作为字符串 所以递归栈执行结束之后，其实就自动进行了一次回溯 dfs(path+s[i]) used[i] = false } } dfs('') return [...new Set(res)] }
2.6 组合总和II 力扣40.组合总和II
2.6.1 问题描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。 示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
2.6.2 问题分析
相对于组合总的第一版本，这个版本的主要有以下的几个问题；
- 候选人编号candidates可以重复
- 每个数字在每个组合只能使用一次
举个简单的例子[1,1,7] , target = 8 元素下标0->2 和元素下标1->2是一样的。 所以在版本一的基础上，我们给先给candidate进行一个排序。在进行横向for循环的时候加一个限制条件，判断是否和上一个元素相同，如果存在相同的直接跳过。
2.6.3 答案
var combinationSum2 = function(candidates, target) { const res = [] // 结果集 const used = [] // 通过下标来记录路径 candidates.sort((a,b)=>a-b) // start->记录下标 sum->当前和 path->选择路径 const dfs = (start,sum,path)=>{ if(sum>=target){ // 递归终止条件 if(sum==target){ res.push(path.slice()) } return } // 横向for循环,start开始避免重复使用同一个元素 for(let i=start;i<candidates.length;i++){ // 下标不同但是结果相同的枝剪掉 if(i!=0&&candidates[i]==candidates[i-1]&&used[i-1]){ continue } used[i] = true path.push(candidates[i]) dfs(i+1,sum+candidates[i],path) path.pop() // 回溯 used[i] = false } } dfs(0,0,[]) return res };
2.7 组合 力扣77.组合
2.7.1 问题描述
给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
你可以按 任何顺序 返回答案。 示例 1：
输入：n = 4, k = 2 输出： [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]
示例 2：
输入：n = 1, k = 1 输出：[[1]]
2.7.2 问题分析
横向for循环:
- 每次从1-n中任意挑选，但是不能
回走也就是 选了3，不要再选1,也不能再选3,这样可以避免结果重复。这个通过start记录下标即可解决 纵向递归: - 递归终止条件为：当前选择路径path的长度等于k
2.7.3 答案
其实写到这里了，如果前面的案例都敲了一边，这个题其实2min就能想出思路来。实现也不难。
var combine = function(n, k) { const res = [] // 处理结果集 // start 记录下标 path记录选择路径 const dfs = (start,path)=>{ if(path.length==k){ // 递归终止条件 res.push(path.slice()) return } for(let i=start;i<=n;i++){ path.push(i) dfs(i+1,path) path.pop() } } dfs(1,[]) return res };
(三) 更多回溯:
- 【简单】257-二叉树的所有路径
- 【中等】17-电话号码的字母组合
- 【中等】79-单词搜索
- 【中等】332-重新安排行程难度提高：
- 【困难】51-N 皇后
- 【中等】377-组合总和 Ⅳ
- 【中等】60-第k个排列难上加难
- 【困难】37-解数独
(四) 总结/结尾
看到这里的一定都是很爱学习的同学吧，没错说的就是你😜。
我们简单总结一下回溯算法的几个特点:
- 回溯算法就是一个不断穷举（递归）的过程，是一种
不撞南墙不回头的算法。 - 很多回溯问题都可以展开为一个
N叉树,通过横向（for循环每一次的选择）,纵向确定递归的终止条件，往往可以很快的写出框架。 - 遇到不太会的一定一定要
画图，一定一定要画图🌍
