回溯法一般用于解决如下几种问题：

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

回溯法解决的问题都可以抽象为树形结构。回溯函数也就是递归函数，指的都是一个函数。

回溯函数遍历过程伪代码如下：

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

​ for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历。这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

分析完过程，回溯算法模板框架如下：

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

组合（可以看成是有序无重复元素的数组）

描述：

1
2
3
4
给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。
示例:
	输入: n = 4, k = 2
	输出: [[2,4],[3,4],[2,3],[1,2],[1,3],[1,4],]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let result = [];
let path = [];
var combine = function(n, k){
    combineHelper(n, k, 1);
    return result;
}
//startIndex用于确认下一层开始的位置，防止重复出现的组合
const combineHelper = (n, k, startIndex)=>{
    //终止条件
    if(path.length===k){
        result.push([...path]);
        return;
    }
    //一层进行处理
    //for循环中的条件为剪枝操作
    //如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了。
    //每一个节点都是一个for循环
    for(let i=startIndex;i<=n-(k-path.length)+1;i++){
        //处理节点
        path.push(i);
        //递归
        combineHelper(n, k, i+1);
        //撤销处理结果，回溯
        path.pop();
    }
}

组合总和iii（可以看成是有序无重复元素的数组）

描述：

1
2
3
4
5
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
说明：所有数字都是正整数。解集不能包含重复的组合。

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

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
let res = [];
let path = [];
var combinationSum = function(k, n){
    const backTracking = (k, n, sum, startIndex)=>{
        if(sum > n)
            return;
        if(path.length===k){
            if(sum===n)
                res.push([...path]);
            return;
        }
        for(let i=startIndex;i<=9-(k-path.length)+1;i++){
            path.push(i);
            backTracking(k, n, sum+i, i+1);
            path.pop();
        }
    }
    backTracking(k, n, 0, 1);
    return res;
}

电话号码的字母组合

描述：

1
2
3
4
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例: 输入："23" 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。
电话号码

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var letterCombinations = function(digits){
    const k = digits.length;
    const map = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    if(k===0)
        return [];
    if(k===1)
        return map[digits].split('');
    let res = [], path = [];
    function backtracking(digits, k, startIndex){
        if(path.length === k){
            res.push(path.join(""));
            return;
        }
        for(const v of map[digits[startIndex]]){
            path.push(v);
            backtracking(digits, k, startIndex+1);
            path.pop();
        }
    }
    backtracking(digits, k, 0);
    return res;
}

组合总和（此题中元素可以重复选取）

描述：

1
2
3
4
5
6
给定一个无重复元素的数组 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] ]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var combinationSum = function(candidates, target){
    const res = [];
    const path = [];
    function backtracking(candidates, target, startIndex, curSum){
        if(curSum>target)
            return;
        if(curSum === target){
            res.push(path);
            return ;
        }
        for(let i=startIndex;i<startIndex.length;i++){
            path.push(candidates[i]);
            //这个地方startindex不用+1是因为元素可以无限重复选取
            backtracking(candidates, target, i, curSum+candidates[i]);
            path.pop();
        }
    }
    backtracking(candidates, target, 0, 0);
    return res;
}

组合总和ii（可以看成是有序有重复元素的数组）

描述：

1
2
3
4
5
给定一个数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用一次。

说明： 所有数字（包括目标数）都是正整数。 解集不能包含重复的组合。

示例：

1
2
输入: candidates = [10,1,2,7,6,1,5], target = 8
所求解集为: [ [1, 7], [1, 2, 5], [2, 6], [1, 1, 6] ]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var sum = function(candidates, target){
    let res = [];
    let path = [];
    candidates.sort((a,b)=>a-b);
    const backtracking = function(candidates, target, curSum, startIndex){
        if(curSum>target)
            return;
        if(curSum===target){
            res.push([...path]);
            return;
        }
        for(let i=startIndex;i<candidates.length;i++){
            // 因为递归的时候下一个startIndex是i+1而不是0所以i>startIndex
            if(i>startIndex&&candidates[i]===candidates[i-1])
                continue;
            path.push(candidates[i]);
            backtracking(candidates, target, curSum+candidates[i], i+1);
            path.pop();
        }
    }
    backtracking(candidates, target, 0, 0);
    return res;
}

分割回文串

描述：

1
2
给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
返回 s 所有可能的分割方案。

示例：

1
2
输入: "aab" 
输出: [ ["aa","b"], ["a","a","b"] ]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function isPalindrome(str){
    let l = 0, r = str.length-1;
    while(l<r){
        if(str[l]!==str[r])
            return false;
        l++;
        r--;
    }
    return true;
}
var partition = function(s) {
    let res = [];
    let path = [];
    function backtracking(startIndex){
        // 只能到最后判断切割是否完毕，而不能当某个串不是回文的时候就返回
        // 因为当前串可能不是回文，但是再添加后面一个字母可能就是回文串了
        if(startIndex>=s.length){
            res.push([...path]);
            return;
        }
        for(let i=startIndex;i<s.length;i++){
            let str = s.slice(startIndex, i+1);
            if(!isPalindrome(str))
                continue;
            path.push(str);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
};

复原IP地址

描述：

1
2
3
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。

示例：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var restoreIpAddress = function(s){
    let res = [], path = [];
    function backtracking(startIndex){
        let len = path.length;
        if(len>4)
            return;
        if(len===4&&startIndex===len){
            res.push(path.join("."));
            return;
        }
        for(let i=startIndex;i<s.length;i++){
            let str = s.slice(startIndex, i+1);
            if(str.length>1&&str[0]==='0')
                break;
            if(+str>255||str.length>3)
                break;
            path.push(str);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
}

子集

描述：

1
2
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例：

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

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
var subsets = function(nums){
    let res = [], path = [];
    function backtracking (startIndex){
        res.push([...path]);
        for(let i=startIndex;i<nums.length;i++){
            path.push(nums[i]);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
}

子集ii

描述：

1
2
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。

示例：

1
2
输入: [1,2,2]
输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var subsets = function(nums){
    let res = [], path = [];
    nums.sort((a,b)=>a-b);
    function backtracking (startIndex){
        res.push([...path]);
        for(let i=startIndex;i<nums.length;i++){
            if(i>startIndex&&nums[i]===nums[i-1])
                continue;
            path.push(nums[i]);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
}

字符串的排列[这题是子集ii、全排列的结合]

链接：

字符串的排列

描述：

​ 输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

示例：

1
2
3
输入："ab"
返回值：["ab","ba"]
说明：返回["ba","ab"]也是正确的

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function Permutation(str)
{
    let res = [], path = [];
    let strarr = str.split('');
    // 不能直接使用arr.sort((a,b)=>a-b)，这样无法比较
    strarr.sort((s,t)=>{
        let a = s.toLowerCase();  
        let b = t.toLowerCase();  
        if (a < b) return -1;  
        if (a > b) return 1;  
        return 0;
    });
    function backtracking(used){
        if(path.length===strarr.length){
            res.push([...path]);
            return;
        }
        for(let i=0;i<strarr.length;i++){
            if(used[i])
                continue;
            if(i>0&&strarr[i]===strarr[i-1]&&!used[i-1])
                continue;
            used[i]=true;
            path.push(strarr[i]);
            backtracking(used);
            used[i]=false;
            path.pop();
        }
    }
    backtracking([]);
    return res.map(item=>item.join(''));
}

递增子序列

描述：

1
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。

示例：

1
2
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var get = function(nums){
    let res = [];
    let path = [];
    function backtracking(startIndex){
        if(path.length>1)
            // 这样不能push完就返回，因为别的长度也可以push进去
            res.push([...path]);
        let used = [];
        for(let i=startIndex;i<nums.length;i++){
            // path当前是递增序列，所以需要nums[i]>path中最后一个值；并且未使用过
            // 记录使用的元素
            if(((path.length>0)&&nums[i]<path[path.length-1])||used[nums[i]+100])
                continue;
            used[nums[i]+100] = true;
            path.push(nums[i]);
            backtracking(i+1);
            path.pop();
        }
    }
    backtracking(0);
    return res;
}

全排列

描述：

1
给定一个 没有重复 数字的序列，返回其所有可能的全排列

示例：

1
2
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
var permute = function(nums) {
    let res = [];
    let path = [];
    // used用于记录使用过的下标
    function backtracking(used){
        if(path.length===nums.length){
            res.push([...path]);
            return;
        }
        for(let i=0;i<nums.length;i++){
            if(used[i])
                continue;
            path.push(nums[i]);
            used[i] = true;
            backtracking(used);
            path.pop();
            used[i] = false;
        }
    }
    backtracking([]);
    return res;
};

全排列ii

描述：

1
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例：

1
2
3
4
5
6
7
示例 1：
输入：nums = [1,1,2]
输出： [[1,1,2], [1,2,1], [2,1,1]]

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

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
var permute = function(nums){
    let res = [];
    let path = [];
    function backtracking(length, used){
        if(path.length===length){
            res.push([...path]);
            return;
        }
        // 既要存储使用过的元素，又要记录使用过的元素下标
        // 使用过的元素不用Pop，使用过的元素下标需要pop
        let usedNum = [];
        for(let i=0;i<length;i++){
            if(used[i]||(usedNum[nums[i]+100]))
                continue;
            path.push(nums[i]);
            usedNum[nums[i]+100] = true;
            used[i] = true;
            backtracking(length, used);
            path.pop();
            used[i] = false;
        }
    }
    backtracking(nums.length, []);
    return res;
}

重新安排行程

描述：

1
2
3
4
5
6
7
	给定一个机票的字符串二维数组 [from, to]，子数组中的两个成员分别表示飞机出发和降落的机场地点，对该行程进行重新规划排序。所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。

提示：
	如果存在多种有效的行程，请你按字符自然排序返回最小的行程组合。例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。
	所有的机场都用三个大写字母表示（机场代码）。
	假定所有机票至少存在一种合理的行程。
	所有的机票必须都用一次 且 只能用一次。

示例：

1
2
3
4
5
6
7
8
示例 1：
输入：[["MUC", "LHR"], ["JFK", "MUC"], ["SFO", "SJC"], ["LHR", "SFO"]]
输出：["JFK", "MUC", "LHR", "SFO", "SJC"]

示例 2：
输入：[["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]]
输出：["JFK","ATL","JFK","SFO","ATL","SFO"]
解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"]。但是它自然排序更大更靠后。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
var findItinerary = function(tickets){
    let res = ['JFK'];
    let map = {};
    for(const ticket of tickets){
        const [from, to] = ticket;
        if(!map[from])
            map[from] = [];
        map[from].push(to);
    }
    for(const city in map)
        map[city].sort();
    function backtracking(){
        if(res.length === tickets.length+1)
            return true;
        // res最后一个一定是from
        if(!map[res[res.length-1]] || !map[res[res.length-1]].length)
            return false;
        for(let i=0;i<map[res[res.length-1]].length;i++){
            let city = map[res[res.length-1]][i];
            // 删除已走过航线，防止死循环
            map[res[res.length-1]].splice(i, 1);
            res.push(city);
            if(backtracking())
                return true;
            res.pop();
            map[res[res.length-1]].splice(i, 0, city);
        }
    }
    backtracking();
    return res;
}

N皇后

描述：

1
2
3
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例：

N皇后 
1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

思路：

  1. 不能同行
  2. 不能同列
  3. 不能同斜线
解法

！！！棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了。

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
var solveNQueens = function(n){
    function isValid(row, col, chessBoard, n){
        // 不能同列
        for(let i=0;i<row;i++)
            if(chessBoard[i][col]==='Q')
                return false;
        // 不能同斜线
        for(let i=row-1, j=col-1;i>=0&&j>=0;i--, j--)
            if(chessBoard[i][j]==='Q')
                return false;
        // 不能同斜线
        for(let i=row-1,j=col+1;i>=0&&j<n;i--,j++)
            if(chessBoard[i][j]==='Q')
                return false;
        // 因为递归是一行一行处理的，所以无需进行不能同行审查
        return true;
    }
    function transformChessBoard(chessBoard){
        let res = [];
        chessBoard.forEach(row=>{
            let rowStr = '';
            row.forEach(value=>{
                rowStr+=value;
            })
            res.push(rowStr);
        })
        return res;
    }
    let res = [];
    let path = new Array(n).fill([]).map(()=>new Array(n).fill('.'));
    function backtracking(row, path){
        if(row===n){
            res.push(transformChessBoard(path));
            return;
        }
        for(let i=0;i<n;i++){
            if(isValid(row, i, path, n)){
                path[row][i]='Q';
                backtracking(row+1, path);
                path[row][i]='.';
            }
        }
    }
    backtracking(0, path);
    return res;
}

解数独

描述：

1
2
3
4
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

示例：

数独 
1
2
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]

解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var solveSudoku = function(board) {
    function isValid(row, col, val, board){
        for(let i=0;i<board.length;i++)
            if(board[i][col]===val)
                return false;
        for(let i=0;i<board.length;i++)
            if(board[row][i]===val)
                return false;
        row = Math.floor(row/3);
        col = Math.floor(col/3);
        for(let i=3*row;i<3*row+3;i++)
            for(let j=3*col;j<3*col+3;j++)
                if(board[i][j]===val)
                    return false;
        return true;
    }
    function backtracking(board){
        for(let i=0;i<board.length;i++){
            for(let j=0;j<board[0].length;j++){
                if(board[i][j]!=='.')
                    continue;
                for(let val=1;val<=9;val++){
                    if(isValid(i, j, `${val}`, board)){
                        board[i][j] = `${val}`;
                        if(backtracking())
                            return true;
                        board[i][j] = '.';
                    }
                }
                return false;
            }
        }
        return true;
    }
    backtracking(board);
    return board;
};

相似的题目：

  • 子集、子集ii、
  • 切割回文串、复原IP地址
  • 去重：组合总和ii、递增子序列、全排列、全排列ii
  • N皇后、解数独、重新安排行程
  • 组合、组合总和iii、电话号码的字母组合、组合总和(可重复)

总结：

  • 结果不包含重复数组：回溯中使用startIndex；输入的数组包含重复元素：去重；
  • 去重的策略：数组排序(i>startIndex)、记录使用过的元素、记录使用过的元素下标(记录使用的下标需要在回溯算法参数中携带此记录数组[需要pop]，记录使用过的元素只需要在回溯算法内部新建数组记录[无需pop])
  • 组合总和ii、组合总和这一类当累积和超过目标值时要及时返回，否则会超时
  • 递增子序列push完当前path后不能马上返回，因为其他长度的也可以push进去

解数独和重新安排行程需要判断回溯结果是否为true，因为这两个问题都只需要找到一个行程就能返回