BackTracking - 回溯算法

## BackTracking - 回溯算法

回溯算法是一种纯暴力的一种算法，它会穷举所有的可能，它本身并不高效，但是对于某些问题只能用这种暴力方法解决。

**回溯产生于递归函数**。在递归函数执行的时候，会有入栈出栈的行为，在程序调用完栈的时候，会回收栈并且返回入栈函数的内存的地址，执行之后的代码。这时候就可以在回收的过程执行其他一些代码操作了

有用过express中间件的同学应该知道。中间件执行的时候有洋葱模型的概念，指的就是从外到内，再从内到外的执行顺序。其实就是入栈出栈的行为导致的顺序问题。

```js
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？该怎么让它自己执行自需的循环次数？

这时候就可以用到回溯算法了。先从口头的方式来去想代码的实现。

![_router_](/Hazlank/blog/blob/master/assets/backtracking-tree.png?raw=true)

从上面的图可以看到，这个数据结构很像一棵树，没错，回溯算法的问题都可以抽象成树形结构来理解，并在遍历树结构的时候产生回溯。

先从```1```开始组合，一直到```3```，发现到了尽头，进行回溯，选择从```3```开始再到```2```，这时候走到尽头发现所有```1```开头的的组合搜索完毕。回溯到最开始并组合以```2```开头的组合，重复以上操作直到```3```组合完毕，所有的组合情况穷举完毕，返回结果。按照以上的想法，就能够实现组合所有的结果，代码怎么实现呢?


### 回溯模板

![_router_](/Hazlank/blog/blob/master/assets/backtracking.png?raw=true)

回溯的模板可以分为三个关键部分

- 从集合里选择元素	 	 (Choice)
- 约束条件                      	 (Constraints)
- 达成目标			             (Goal)

第一个部分。我们需要从当前集合选择哪一个元素
比如上面的集合[1,2,3]写为
```js
for(var i = 0; i < nums.length; i++) {
	//choice nums[i]
	//backtracking()
	//undo choice nums[i]
}
```

第二个，我们需要一定的约束条件,比如选过一次就不用再选了
```js
for(var i = 0; i < nums.length; i++) {
	if (!choices[i]) {
		//choice nums[i]
		//backtracking()
		//undo choice nums[i]
	}
}
```
choices可以用简单的数组结构来表示当前数字是否被使用


最后，在达成正确结果的时候需要做的事情。比如，当我们组合的数字长度达到数组长度的时候就返回并保存结果
```js
if (premute === nums.length) {
	// add solution to result
	return
}
```

三个重要的部分都有了，进行组合，最终全排列的代码如下
```js
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（深度优先遍历）产生的操作。就像是遍历二叉树的时候，递归并将输出代码的放在不同位置就能够进行前中后序遍历。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

BackTracking - 回溯算法 #12