BackTracking - 回溯算法

[Hazlank]

BackTracking - 回溯算法

回溯算法是一种纯暴力的一种算法，它会穷举所有的可能，它本身并不高效，但是对于某些问题只能用这种暴力方法解决。

回溯产生于递归函数。在递归函数执行的时候，会有入栈出栈的行为，在程序调用完栈的时候，会回收栈并且返回入栈函数的内存的地址，执行之后的代码。这时候就可以在回收的过程执行其他一些代码操作了

有用过express中间件的同学应该知道。中间件执行的时候有洋葱模型的概念，指的就是从外到内，再从内到外的执行顺序。其实就是入栈出栈的行为导致的顺序问题。

app.use(next => {
  console.log(1)
  next()
  console.log(2)
})

app.use(next => {
  console.log(3)
  next()
  console.log(4)
})

//print 1 3 4 2

举个题目例子直接讲解回溯算法吧

全排列

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

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

一开始大家可能会想，可以对每个数字进行遍历，可以写三个for循环，但是如果集合多起来了呢？那是不是要写N个for？该怎么让它自己执行自需的循环次数？

这时候就可以用到回溯算法了。先从口头的方式来去想代码的实现。

从上面的图可以看到，这个数据结构很像一棵树，没错，回溯算法的问题都可以抽象成树形结构来理解，并在遍历树结构的时候产生回溯。

先从1开始组合，一直到3，发现到了尽头，进行回溯，选择从3开始再到2，这时候走到尽头发现所有1开头的的组合搜索完毕。回溯到最开始并组合以2开头的组合，重复以上操作直到3组合完毕，所有的组合情况穷举完毕，返回结果。按照以上的想法，就能够实现组合所有的结果，代码怎么实现呢?

回溯模板

回溯的模板可以分为三个关键部分

• 从集合里选择元素 (Choice)
• 约束条件 (Constraints)
• 达成目标 (Goal)

第一个部分。我们需要从当前集合选择哪一个元素
比如上面的集合[1,2,3]写为

for(var i = 0; i < nums.length; i++) {
	//choice nums[i]
	//backtracking()
	//undo choice nums[i]
}

第二个，我们需要一定的约束条件,比如选过一次就不用再选了

for(var i = 0; i < nums.length; i++) {
	if (!choices[i]) {
		//choice nums[i]
		//backtracking()
		//undo choice nums[i]
	}
}

choices可以用简单的数组结构来表示当前数字是否被使用

最后，在达成正确结果的时候需要做的事情。比如，当我们组合的数字长度达到数组长度的时候就返回并保存结果

if (premute === nums.length) {
	// add solution to result
	return
}

三个重要的部分都有了，进行组合，最终全排列的代码如下

function permute(nums) {
    var res = []
    var len = nums.length
    var used = new Array(len).fill(false)

    var backtracking = function(permutations = []) {
        if (permutations.length === len) {
            res.push([...permutations])
            return
        }
        for (var i = 0; i < len;i++) {
            if (!used[i]) {
                used[i] = true
                permutations.push(nums[i])
                backtracking(permutations)
                used[i] = false
                permutations.pop()
            }
        }
    }

    backtracking()
    return res
}

比较难理解的可能就是中间递归的部分

让我们来拆解一下步骤。第一次for循环拿到1，并设置为不可选取的值，开始进行递归。又一次进入for循环，但是发现1并不能拿了，需要从2开始拿，并再次递归后只能拿到3,到3递归的时候，达成了我们想要的目标长度[1,2,3]，将其添加到结果集并返回。

这时候会触发return，开始进行出栈，这就是回溯的开始。

出栈的地址指向第三层递归循环3的backtracking，然后执行后面的代码,将3弹出并将其used值改为false，循环条件达到终点，不再继续循环。继续执行出栈到第二层递归的backtracking，将2弹出并将其used值改为false。

到关键的一步了，这时候for只循环到2，也就是说，循环还没结束，需要继续进行循环3，并将3装到集合里[1,3],发现长度没有满足条件，得继续递归取值，但这时候也只能拿到2了，到这一步后，开始回收栈，第二层递归的循环也结束了，将会返回到第一层递归的for循环，将1弹出，至此，所有1开头的结果组合完毕，将会从2开始，并重复1的递归步骤。将所有可能性的结果保存起来。

剪枝

回溯法能够做到最好的优化，就是进行剪枝，树枝就是我们的循环路径，我们可以通过条件跳过某些路径来省略没必要的循环。

回溯解决问题

回溯主要解决一些需要满足所有组合的问题。比如N皇后，数独，排列问题，1~N个数按规则找出加起来等于k数的集合等等...

总结

回溯用了递归函数，不断的调用循环，来穷举所有的可能性。并且在入栈出栈的时候达成约束条件，再利用条件约束不合适的结果。

回溯的问题可以抽象成树，而且，它就是dfs（深度优先遍历）产生的操作。就像是遍历二叉树的时候，递归并将输出代码的放在不同位置就能够进行前中后序遍历。