什么是回溯

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
在二叉树系列中，我们已经不止一次，提到了回溯，例如二叉树：以为使用了递归，其实还隐藏着回溯(opens new window)。
回溯是递归的副产品，只要有递归就会有回溯。

应用场景

组合问题：N个数里面按一定规则找出k个数的集合
切割问题：一个字符串按一定规则有几种切割方式
子集问题：一个N个数的集合里有多少符合条件的子集
排列问题：N个数按一定规则全排列，有几种排列方式
棋盘问题：N皇后，解数独等等

理解回溯法

回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构！
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一颗高度有限的树（N叉树）。

回溯法模板

回溯法三步曲

1、确定方法参数

伪代码如下：

void backtracking(参数)

2、确定终止条件

伪代码如下：

if (终止条件) {
    存放结果;
    return;
}

3、搜索遍历

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

如图：

集合的大小决定了for循环横向遍历，递归的深度（即：到达条件时递归的深度）决定树的深度。

伪代码如下：

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

模板代码

综上，回溯算法模板框架，如下：

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

参考

回溯算法理论基础

算法案例

组合

电话号码的字母组合

题解

const letterCombinations = function (digits) {
    const digitsLen= digits.length;
    const letterMap = [" ", " ", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"];
    // 处理非法情况
    if (!digitsLen) return [];
    // 处理长度为1的情况
    if (digitsLen === 1) {
        return letterMap[digits[0]].split('');
    }
    const res = [], path =[];
    backtracking(0);
    return res;
    function backtracking(index) {
        if (index === digitsLen) {
            res.push(path.join('').trim());
            return;
        }
        for(const v of letterMap[digits[index]]) {
            path.push(v);
            backtracking(index + 1);
            path.pop();
        }
    }
};
const res = letterCombinations('21');
console.log(res)

组合

图解

[77] 组合.png

题解

/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
    // n - 集合遍历的广度
    // k - 递归的深度
    // 存放结果
    var res = [];
    // 符合条件单一结果
    var item = [];
    // 遍历集
    var list = [];
    for (var i = 0; i < n; i++) {
        list.push(i+1);
    }
    backtracking(0, list)
    function backtracking(startIndex, path) {
        if (item.length === k) {    // 符合条件终止
            // 存入结果
            res.push([].concat(path));
            return;
        }
        for (var i = startIndex, l = list.length; i < l; i++) { // 遍历本节点子集
            var trackItem = list[i];
            item.push(trackItem);
            backtracking(i+1, item);
            // 回溯
            item.pop();
        }
    }
    return res;
};