原文链接：https://www.cnblogs.com/yalong/p/16798569.html
回溯算法
回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
什么问题适合用回溯算法
- 有很多路
- 路里面有死路， 也有出路
- 通常需要用递归来模拟所有的路
今天我们就用这个 "通用解题方法" 来解决leetcode 上几个常见的题目
全排列
解题思路：
用递归模拟全部的路，直到path 长度等于 nums 长度，这就到了死路，就可以结束递归
代码如下：
var permute = function(nums) {
let res = []
let fn = (path) => {
if(path.length === nums.length) {
res.push(path)
return
}
nums.forEach(item => {
if (!path.includes(item)) {
fn(path.concat(item))
}
})
}
fn([])
return res
};
子集
解题思路
跟上面的全排列类似，不过不能包含重复的子集，比如 123 跟 321 其实是相同的子集
那么我们在查找的时候，只要按照下标 index 从小到大查找，就可以避免321 这种排列的子集了
由于要找到全部子集，所以子集的长度可以是0-nums.length 之前的任意长度 n
递归函数结束的条件 就是 path 的长度 等于 n
代码
var subsets = function(nums) {
const res = [];
const backtrack = (path, l, start) => {
if (path.length === l) {
res.push(path)
return;
}
for(let i=start; i<nums.length; i++) {
backtrack(path.concat(nums[i]), l, i + 1)
}
}
for (let i = 0; i <= nums.length; i++) {
backtrack([], i, 0)
}
return res;
}
递增子序列
解题思路
跟上面的 【子集】相似，不过在递归之前需要判断下，path中新加入的数必须大于等于 path 中最后一位数
比如数组 [1，2，3，3] 查找出来的结果包中有 123 123 这俩3 是不同位置的，但是输出的结果 只能有一个 123 就行了， 所以我们需要对结果进行一个去重处理
代码
var findSubsequences = function(nums) {
const res = [];
let obj = {}
const backtrack = (path, l, start) => {
if (path.length === l) {
if (path.length > 1) { // 这里是去重
let subStr = path.join(',')
if (!obj[subStr]) {
obj[subStr] = true
res.push(path)
}
}
return;
}
for(let i=start; i<nums.length; i++) {
// 在加入数组之前 做个判断 如果数组有长度的话， 数组最后一位必须小于等于 num[i]
if ((path.length && path[path.length - 1] <= nums[i]) || !path.length) {
backtrack(path.concat(nums[i]), l, i + 1)
}
}
}
for (let i = 0; i <= nums.length; i++) {
backtrack([], i, 0)
}
return res;
};
总结
凡是这种有很多路，并且有出路 也有死路的题目，都可以用回溯算法进行处理
记得递归函数一定要有结束条件，不然就陷入死循环了