回溯算法总结

发表于 | 分类于

解题模板

解决一个回溯问题，实际上就是一个决策树的遍历过程。你只需要思考 3 个问题：

  1. 路径：也就是已经做出的选择

  2. 选择列表：也就是你当前可以做的选择

  3. 结束条件：也就是到达决策树底层，无法再做选择的条件

回溯算法的模板代码：

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
  if 满足结束条件:
    result.push(路径)
    return

  for 选择 in 选择列表:
    做选择
    backtrack(路径, 选择列表)
    撤销选择

其核心就是 for 循环里面的递归，在递归调用之前「做选择」，在递归调用之后「撤销选择」

案例代码

最基础，直接套模板

46. 全排列

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
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    let result = [] // 结果数组
    let track = [] // 路径
    const backtrack = function (track, nums) {
        if (track.length === nums.length) { // 满足条件结束
            let array = JSON.parse(JSON.stringify(track))
            result.push(array)
            return
        }
        for (let i = 0; i < nums.length; i++) {
            // 剔除已经存在的
            if (track.indexOf(nums[i]) > -1) {
                continue
            }
            // 做选择
            track.push(nums[i])
            // 进入下一层决策树
            backtrack(track, nums)
            // 撤销选择
            track.pop()
        }
    }
    backtrack(track, nums)
    return result
};

39. 组合总和

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
/**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 * 暴力
 */
var combinationSum = function(candidates, target) {
    let stringArray = []
    let track = []
    let total = 0
    backTrack(candidates, track, total)

    let resultArray = Array.from(new Set(stringArray)) // 过滤重复
    return resultArray.map(item => { // 返回数组
        return item.split(' ')
    })
    function backTrack(candidates, track, total) {
        if (total > target) {
            return
        }
        if (total === target) {
            let array = JSON.parse(JSON.stringify(track))
            // 存储好排序的字符串，用于过滤重复项
            array = array.sort((a, b) => {
                return a - b
            })
            stringArray.push(array.join(' '))
            return
        }
        for (let i = 0; i < candidates.length; i++) {
            track.push(candidates[i])
            total += candidates[i]
            backTrack(candidates, track, total)
            // 回溯
            track.pop()
            total -= candidates[i]
        }
    }
};

进阶

进阶题一般需要保证要去除重复项，所以一般会有一个数组用来记录已经走过的路径或者选过的值

剑指 Offer 38. 字符串的排列

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
/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
    if (s === '') {
        return []
    }
    let resultArray = []
    let trackString = ''
    let visibed = {} // 用于记录已经添加过的字符索引
    backTrack(s, trackString)
    function backTrack(s, trackString) {
        if (trackString.length === s.length) {
            resultArray.push(trackString)
            return
        }
        for (let i = 0; i < s.length; i++) {
            if (visibed[i]) {
                continue
            }
            visibed[i] = true // 记录当前添加的索引
            trackString += s[i]
            backTrack(s, trackString)
            trackString = trackString.slice(0, trackString.length - 1)
            visibed[i] = false // 测回当前添加的索引记录
        }
    }
    return Array.from(new Set(resultArray))
};

77. 组合

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
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 * 把 n  转化为 1 - n 的数组,即变成了带不能使用重复索引的 k 个数的全排列
 */
var combine = function(n, k) {
    // 初始化数组
    let array = new Array(n).fill(0)
    let candidates = array.map((item, index) => {
        return index + 1
    })
    let resultArray = [] // 结果数组
    let track = []
    let visited = {} // 记录 candidates 中已经添加过的索引
    backTrack(candidates, track)
    return resultArray

    function backTrack(candidates, track) {
        if (track.length === k) {
            let array = JSON.parse(JSON.stringify(track))
            resultArray.push(array)
            return
        }
        for (let i = 0; i < candidates.length; i++) {
            if (visited[i]) {
                return
            }
            visited[i] = true
            track.push(candidates[i])
            backTrack(candidates, track)
            track.pop()
            visited[i] = false
        }
    }
};

困难

困难题目一般除了要利用回溯之外，还需要对选择的值做一些额外的判断是否满足可选中的要求，典型的如 51. N 皇后 问题:

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/**
 * @param {number} n
 * @return {string[][]}
 */
/* 输入棋盘边长 n，返回所有合法的放置 */
var solveNQueens = function(n) {
    // 初始化棋盘格
    let board = new Array(n)
    for (let i = 0; i < board.length; i++) {
        board[i] = new Array(n).fill('.')
    }
    let resultArray = [] // 结果数组
    backtrack(board, 0)
    return resultArray
    /* 递归回溯 */
    // 路径：board 中小于 row 的那些行都已经成功放置了皇后
    // 选择列表：第 row 行的所有列都是放置皇后的选择
    // 结束条件：row 超过 board 的最后一行
    function backtrack (board, row) {
        // 满足结束条件
        if (row === board.length) {
            let newBoard = JSON.parse(JSON.stringify(board))
            let stringsBoard = []
            for (let i = 0; i < n; i++) {
                stringsBoard[i] = newBoard[i].join(''); // 将每一行拼成字符串
            }
            resultArray.push(stringsBoard)
            return
        }
        // 遍历选择
        for (let col = 0; col < board[row].length; col++) {
            // 去除不合法的选择
            if (!isValid(board, row, col)) {
                continue
            }
            // 做选择
            board[row][col] = 'Q'
            // 进入下一行决策
            backtrack(board, row + 1)
            // 撤回选择
             board[row][col] = '.'
        }
    }

    /* 是否可以在 board[row][col] 放置皇后？ */
    function isValid(board, row, col) {
        let n = board.length;
        // 检查列是否有皇后互相冲突
        for (let i = 0; i < n; i++) {
            if (board[i][col] == 'Q')
                return false;
        }
        // 检查右上方是否有皇后互相冲突(右边对角线，只要检测上方，下方肯定不冲突))
        for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q')
                return false;
        }
        // 检查左上方是否有皇后互相冲突（左对角线，只要检测上方,下方肯定不冲突）
        for (let i = row - 1, j = col - 1;i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q')
                return false;
        }
        return true;
    }
};

其它类似

17. 电话号码的字母组合

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
/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits === '') {
        return []
    }
    let resultArray = [] // 结果数组
    // 初始化选择列表
    let stringArray = [
        ['a','b','c'],
        ['d','e','f'],
        ['g','h','i'],
        ['j','k','l'],
        ['m','n','o'],
        ['p','q','r','s'],
        ['t','u','v'],
        ['w','x','y','z']
    ]
    let array = []
    for (let i = 0; i < digits.length; i++) {
        let item = Number.parseInt(digits[i])
        array.push(stringArray[item - 2])
    }
    backTrack(array, [])

    // 路径记录在 track 数组中
    // 选择列表，动态根据 array 判断
    // 结束条件 track.length === array.length   
    function backTrack (array, track) {
        if (track.length === array.length) {
            resultArray.push(track.join(''))
            return
        }
        let stringArray = array[track.length]
        for (let i = 0; i < stringArray.length; i++) {
            let newTrack = JSON.parse(JSON.stringify(track)) // 处理数组浅拷贝引用问题
            newTrack.push(stringArray[i])
            backTrack(array, newTrack)
        }
    }
    return resultArray
}

思路来自: labuladong的算法小抄