❝弱小和无知不是生存的障碍，傲慢才是 --《三体·死神永生》
❞
大家好，我是「柒八九」。
今天，我们继续探索JS算法相关的知识点。我们来谈谈关于「回溯法」的相关知识点和具体的算法。
如果，想了解其他数据结构的算法介绍，可以参考我们已经发布的文章。如下是算法系列的往期文章。
好了，天不早了，干点正事哇。
❝❞
何为回溯法 集合的组合、排列 利用回溯算法解决其他问题
❝回溯法可以看做「暴力法的升级版」,它在解决问题时的每一步都「尝试所有可能的选项」，最终「找出所有可行的解决方案」。
❞
回溯法非常适合解决「由多个步骤组成的问题，并且每个步骤都有多个选项」。
❝用回溯法解决问题的过程可以形象的「用一个树形结构表示，求解问题的每个步骤可以看作树中的一个节点」。如果在某一步有
❞n个可能的「选项」，那「每个选项是树中的一条边」，经过这些边就可以到达该节点的n个子节点。
在采用回溯法解决问题时，
❝因此，采用回溯法解决问题的过程实质上是在树形结构中从根节点开始进行「深度优先遍历」
❞
通常，回溯法的深度优先遍历用「递归」代码实现。
如果在前往某个节点时对问题的解的「状态进行了修改」，那么在回溯到它的父节点时，要「清除相应的修改」。
由于回溯法是在所有选项形成的树上进行深度优先遍历，如果解决问题的步骤较多或每个步骤都面临多个选项，那么遍历整颗树将需要较多的时间。如果明确知道某些子树没有必要遍历，那么在遍历的时候应该避开这些子树以优化效率。 通常将使用回溯法时避免遍历不必要的子树的方法称为「剪枝」。
从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）形成一个子集。一个子集又称为一个组合。如果两个子集（组合）的元素完全相同只是顺序不同，那么它们可以看作同一个子集（组合）。
从一个包含m个元素的集合中挑选出n个元素（0≤n≤m）并按照某种顺序形成一个「排列」。 m等于n的排列有称为「全排列」。如果两个排列的元素完全相同只是顺序不同，那么它们就是两个不同的排列。 「排列与元素的顺序相关」。
题目描述：
❝输入一个「不含重复数字」的数据集合，请找出它的「所有」子集
❞
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
n个元素，那么生成子集可以分为n步」 function subsets(nums){
let result = [];
if(nums.length == 0) return result;
(function helper(nums,index,subset,result){
if(index === nums.length){ // 基线条件
result.push([...subset])
}else if(index < nums.length){
helper(nums,index + 1, subset,result); // 不将数字添加到子集
subset.push(nums[index]); // 将数字添加到子集中
helper(nums,index + 1,subset,result);
subset.pop();
}
})(nums,0,[],result)
return result;
}
代码解释
helper有四个参数 nums 是数组 nums,包含输入集合的所有数字。可以逐一从集合中 「取出一个数字并选择是否将数字添加到子集中」。 index是当前取出的数字在数组 nums中下标 subset是 「当前子集」 result是 「所有已经生成」的子集 nums中取出一个下标为 index的数字时，都要考虑是否将该数字添加到子集 subset中。 helper处理数组nums中的下一个数字(下标增加1)」 helper(nums,index + 1,subset,result) index的数字添加到子集subset中」。 subset.push(nums[index]) nums下一个数字( 下标增加1) helper(nums,index + 1, subset, result) helper也执行完成，接下来将回溯到前一个数字的函数调用处继续执行。」 subset.pop() index等于数组nums的长度时候」，表示数组中的所有数字都已经处理过，因此可以生成一个子集。将子集 subset添加到 result中 subset的副本，因为接下来还需要修改 subset用以获得其他的子集 result.push([...subset]) 题目描述：
❝输入
❞n和k，请输入从1到n中选取k个数字组成的所有「组合」。
输入：n = 3, k = 2
输出：[[1,2],[1,3],[2,3]]
k个数字的组合 function combine(n,k){
let result = [];
(function helper(n,k,index,subset,result){
if(subset.length === k){ // 基线条件
result.push([...subset])
}else if(index <= n){
helper(n,k, index + 1, subset,result); // 不将数字添加到子集
subset.push(index); // 将数字添加到子集中
helper(n,k,index + 1,subset,result);
subset.pop();
}
})(n,k,1,[],result)
return result;
}
代码解释
helper有五个参数 n 是数组范围 1~n k是组合的长度 index是当前取出的数字 subset是当前子集 result是所有 「已经生成」的子集 subset.length等于 k时，进行子集的收集处理 result.push([...subset]) index是从 1开始的。 题目描述：
❝给定一个「没有重复数字」的正整数集合，请找出所有元素之和等于某个给定值(
❞target)的所有组合。
同一个数字可以在组合中「重复任意次」。
输入：candidates = [2,3,6,7], target = 7
输出：[[7],[2,2,3]]
i的数字,此时， 「面临两个选择」。 i + 1的数字。 i的数字。 function combinationSum(nums,target){
let result = [];
(function helper(nums,target,index,subset,result){
if(target ==0){ //基线条件
result.push([...subset])
}else if(target > 0 && index < nums.length){
helper(nums,target,index + 1,subset,result); // 不将数字添加到子集
subset.push(nums[index]); // 将数字添加到子集中
helper(nums,target - nums[index],index,subset,result);
subset.pop();
}
})(nums,target,0,[],result)
return result;
}
代码解释
nums[index]可能在组合中 「重复出现」，因此在 index处， 「选择了将数字添加到组合」的选择， 「递归调用helper时，index是不需要+1的」。 target target - nums[index] target为 0时，说明现在 「子集」已经满足情况。 result.push([...subset]) target只能少，不能多，所以可以判断 target与 0的关系，来进行 「剪枝」处理。 if(target>0 && index < nums.length) 上面的几个题目都是关于数学上的组合、集合，其实这些「模型」可以应用到很多其他问题中。
例如，当客人走近餐厅准备吃饭，一种点菜的方法就是生成一个符合条件的组合。
k道菜」，那么就是找出 「包含k个元素」的所有符合条件的组合 题目描述：
❝给定一个可能「包含重复数字」的整数集合，请找出所有元素之和等于某个给定值（
❞target）的所有组合。
输出中不得包含重复的组合。
输入：candidates = [2,5,2,1,2], target = 5
输出：[[1,2,2],[5]]
m的数字时，跳过所有值为m的数字。」 function combinationSum(nums,target){
nums.sort((a,b) => a -b);
let result = [];
(function helper(nums,target,index,subset,result){
if(target == 0){ // 基线条件
result.push([...subset]);
}else if(target > 0 && index < nums.length){
// 选择跳过某批值相同的数字
helper(nums,target,getNext(nums,index),subset,result);
subset.push(nums[index]);
helper(nums,target - nums[index], index + 1,subset,result);
subset.pop();
}
})(nums,target,0,[],result)
return result;
}
辅助函数
function getNext(nums,index){
let next = index;
while(next < nums.length && nums[next] == nums[index]){
next++;
}
return next;
}
代码解释
getNext找到与当前 index值不同的下标 题目描述：
❝给定一个「没有重复数字」的集合，请找出它的所有全排列。
❞
输入：nums = [0,1]
输出：[[0,1],[1,0]]
n个元素， n步 n个选项 n-1个选项 n步，每一步面临着若干选项」 -- 「回溯法」 function permute(nums){
let result = [];
(function helper(nums,index,result){
if(index == nums.length){
result.push([...nums]) // 基线条件
}else {
for(let j = index;j<nums.length;j++){
swap(nums,index,j); // 数字替换位置
helper(nums,index + 1,result);
swap(nums,index,j); // 清除对排列状态的修改
}
}
})(nums,0,result)
return result;
}
辅助函数
const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];
代码解释
nums保存着当前排列的状态」 helper生成排列的下标为 index的数字时， 0到 index-1的数字都 「已经选定」， nums中下标从 index到 n-1的数字(假设数组的长度为 n)都有可能放到排列的下标为 index的位置 helper中 「有一个for循环逐一用下标为index的数字交互它后面的数字」。 for循环包含下标为 index的数字本身，因为它自己也能放在排列下标为 index的位置 swap(nums,index,j) index + 1的数字 helper(nums,index + 1, result) swap(nums,index,j) 题目描述：
❝给定一个包含「重复数据」的集合，请找出它的所有全排列
❞
输入：nums = [1,1,2]
输出：[[1,1,2],[1,2,1],[2,1,1]]
i个数字时，如果已经将某个值为 m的数字交换为排列的第 i个数字，那么再遇到其他值为 m的数字就 「跳过」 function permuteUnique(nums){
let result = [];
(function helper(nums,index,result){
if(index === nums.length){
result.push([...nums]); // 基线条件
}else {
let map = {};
for(let j = index;j<nums.length;j++){
if(!map[nums[j]]){
map[nums[j]] = true;
swap(nums,index,j);
helper(nums,index + 1,result);
swap(nums,index,j);
}
}
}
})(nums,0,result)
return result;
}
辅助函数
const swap = (nums,i,j) => [nums[i],nums[j]] = [nums[j],nums[i]];
代码解释
map，来保存已经交换到排列下标为index的位置的所有值」。 index位时才做交换，否则直接跳过 for循环中多一层判断 if(!map[nums[j]]) 除了可以解决与集合排列、组合相关的问题，回溯法还能解决很多问题。
如果解决一个问题需要「若干步骤」，并且每一步都面临「若干选择」，当在「某一步」做了某个选择之后，前往下一步仍然面临若干选项。那么可以考虑用「回溯法」
❝通常，回溯法可以用「递归代码」实现。
❞
题目描述：
❝输入一个正整数
❞n,请输出「所有」包含n个左括号和n个右括号的组合，要求每个组合的左括号和右括号匹配。
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
n，生成的括号组合包含 n个左括号和 n个右括号。 2n步，每一步生成一个括号 n个 function generateParenthesis(n){
let result = [];
(function helper(left,right,subset,result){
if(left == 0 && right ==0){
result.push(subset); //基线条件
return ;
}
// 已经生成的左括号的数目少于`n`个
if(left > 0){
helper(left -1,right,subset + "(",result)
}
// 已经生成的右括号的数目少于已经生成的左括号的数目
if(left < right){
helper(left,right -1,subset + ")",restule)
}
})(n,n,"",result)
return result;
}
代码解释
left:表示 「还需要生成」的左括号的数目 right：表示 「还需要生成」右括号的数目。 left-1;每生成一个右括号，参数 right -1;当 left/right都等于 0，一个完整的括号组合生成 result.push(subset); n个」( left>0)就能生成一个左括号 left < right）就能生成一个右括号 题目描述：
❝输入一个字符串，要求将它「分割成若干子字符串，使每个字符串都是回文」。
❞
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
n个字符，那么面临 n个选项 1的字符串（只包含该字符） 2的字符串（包含该字符及它后面的一个字符） x的字符串 ( x<n) n的字符串 function partition(str){
let result = [];
(function heler(str,start,subset,result){
if(start == str.length){
result.push([...subset]); // 基线条件
}else {
for(let i = start;i<str.length;i++){
if(isPalinadrome(str,start,i)){
subset.push(str.substring(start,i+1));
helper(str,i + 1,subset,result);
subset.pop();
}
}
}
})(str,0,[],result)
return result;
}
辅助函数
function isPalinadrome(str,start,end){
while(start < end){
if(str[start++]!=str[end--]) return false;
}
return true
}
代码解释
start的字符串时，用一个 for循环逐一判断从下标 start开始到 i结束的每个子字符串是否会回文 i从下标 start开始，到字符串 s的最后一个字符结束 subset中 subset.push(str.substring(start,i+1)) （ substring它的第一个参数表示子字符串的开始位置，第二个位置表示结束位置--返回结果不含该位置） i+1开始的剩余字符串。 ❝如果解决一个问题需要若干步骤，并且在每一步都面临着若干选项，那么可以尝试用「回溯法」解决问题。
❞
应用回溯法能够解决「集合的排列、组合」的很多问题。
❝回溯法都可以使用「递归」的代码实现。递归代码需要先确定「递归退出」的边界条件(基线条件)，然后逐个处理集合中的元素。
❞
对于「组合类」问题，每个数字都面临两个选项
对于「排列类」问题，一个数字如果后面有n个数字，那么面临n+1个选择，即可以将数字和后面的数字(包括它自身)交换。
「分享是一种态度」。
参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版
「全文完，既然看到这里了，如果觉得不错，随手点个赞和“在看”吧。」
本文由 mdnice 多平台发布
本文发布于:2024-02-01 17:42:44，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170678150138383.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
