算法总结——JS实现回溯

算法总结——JS实现回溯

目录

一、回溯定义

百度百科

其他

二、回溯模板 

三、几个例题

组合

电话号码的字母组合

一、回溯定义

百度百科

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

其他

从解决问题每一步的所有可能选项里系统选择出一个可行的解决方案。

在某一步选择一个选项后，进入下一步，然后面临新的选项。重复选择，直至达到最终状态。

回溯法解决的问题的所有选项可以用树状结构表示。

• 在某一步有n个可能的选项，该步骤可看作树中一个节点。
• 节点每个选项看成节点连线，到达它的n个子节点。
• 叶节点对应终结状态。
• 叶节点满足约束条件，则为一个可行的解决方案。
• 叶节点不满足约束条件，回溯到上一个节点，并尝试其他叶子节点。
• 节点所有子节点均不满足条件，再回溯到上一个节点。
• 所有状态均不能满足条件，问题无解。

二、回溯模板 

三部曲：

• 递归函数的返回值以及参数

在这里要定义两个全局变量，一个用来存放符合条件单一结果，一个用来存放符合条件结果的集合。

• 回溯函数终止条件
• 单层搜索的过程

回溯法的搜索过程就是一个树型结构的遍历过程，for循环用来横向遍历，递归的过程是纵向遍历。

let result=[]
function backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

三、几个例题

组合

对应LeetCode 77.组合

给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

示例:
输入: n = 4, k = 2
输出:
[
[2,4],
[3,4],
[2,3],
[1,2],
[1,3],
[1,4],
]

/*** @param {number} n* @param {number} k* @return {number[][]}*/
var combine = function(n, k) {let res=[],path=[]combineHelper(n,k,1)return resfunction combineHelper(n,k,startIndex){if(path.length===k){res.push([...path])// res.push(path) // 这里Push的元素是一个数组，引用类型，后面path.pop后，元素又改了！！！// 所以这里要拷贝一份才行！！！而解构可以解决这个问题return}for(let i=startIndex;i<=n-(k-path.length)+1;i++){   //这里做了剪枝优化，i<=n也可以path.push(i)combineHelper(n,k,i+1)path.pop()}}
};

电话号码的字母组合

对应LeetCode 17.电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

/*** @param {string} digits* @return {string[]}*/
var letterCombinations = function(digits) {const k=digits.length//0-9代表不同的字符，正好用数组存储方便const map = ["","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]if(k===0) return []if(k===1) return map[digits].split('')let res=[],path=[]backTracking(digits,k,0)return res//1.确定参数，首先是输入的电话号码，其次它的长度，最后是到第几个了//2.终止条件，到最后一个号码，存进去//3.单层遍历是每一个号码，下一层是后一个号码function backTracking(n,k,a){if(path.length===k){res.push(path.join(''))return}for(const m of map[n[a]]){path.push(m)backTracking(n,k,a+1)path.pop()}}};

组合总和

对应LeetCode 39.组合总和

给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的数字可以无限制重复被选取。

说明：

• 所有数字（包括 target）都是正整数。
• 解集不能包含重复的组合。

示例 1： 输入：candidates = [2,3,6,7], target = 7, 所求解集为： [ [7], [2,2,3] ]

示例 2： 输入：candidates = [2,3,5], target = 8, 所求解集为： [   [2,2,2,2],   [2,3,3],   [3,5] ]

/*** @param {number[]} candidates* @param {number} target* @return {number[][]}*/
var combinationSum = function(candidates, target) {let res=[],path=[]candidates.sort((a,b)=>a-b) //先排序backTracking(candidates,target,0,0)return res//这个区别就是每一层都是从i开始进行的，不是i+1，说明可以重复function backTracking(n,target,sum,startIndex){if(sum>target){return}if(sum===target){res.push([...path])return}for(let i=startIndex;i<n.length;i++){sum+=n[i]path.push(n[i])backTracking(n,target,sum,i)path.pop()sum-=n[i]}}
};