跳到主要内容

回溯算法

理论知识​

什么是回溯法​

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

回溯法的效率​

回溯法的性能如何呢，这里要和大家说清楚了，虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

那么既然回溯法并不高效为什么还要用它呢？

因为没得选，一些问题能暴力搜出来就不错了，撑死了再剪枝一下，还没有更高效的解法。

回溯法解决的问题​

回溯法，一般可以解决如下几种问题：

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

相信大家看着这些之后会发现，每个问题，都不简单！

另外，会有一些同学可能分不清什么是组合，什么是排列？

组合是不强调元素顺序的，排列是强调元素顺序。

例如：{1, 2} 和 {2, 1} 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，{1, 2} 和 {2, 1} 就是两个集合了。

记住组合无序，排列有序，就可以了。

如何理解回溯法​

回溯法解决的问题都可以抽象为树形结构，是的，我指的是所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度（一般for循环来处理），递归的深度就构成了树的深度（一般递归来处理）。

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

回溯法模板​

这里给出Carl总结的回溯算法模板。回溯三部曲：

  1. 回溯函数模板返回值以及参数

    • 因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数

  2. 回溯函数终止条件

    • 什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

  3. 回溯搜索的遍历过程

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

    • 回溯算法理论基础

    • for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

    • backtracking这里自己调用自己，实现递归。

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

void backtracking(参数){
    if(终止条件){
        // 一般情况下，终止条件就到了我们收集结果的时候了，大部分情况下都是会在叶子节点的时候去收集结果，有的会在每个节点就去收集结果
        收集结果
        return;
    }
    
    // 进入单层搜索的逻辑，一般情况下是一个for循环，用来处理这个集合中的每一个元素
    for(集合的元素集){
        处理节点（处理满足条件的节点）
        递归函数（进入递归的过程）
        回溯操作（撤销处理节点的情况）
    }
}

组合​

https://programmercarl.com/0077.%E7%BB%84%E5%90%88.html

https://leetcode.cn/problems/combinations/description/

思路​

从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。所以需要startIndex来记录下一层递归，搜索的起始位置。

77.组合2

未剪枝​

var combine = function(n, k) {
    
    const arr = []
    const result = []

    function backtracking(startIndex){
        if(arr.length === k){
            result.push([...arr])
            return
        }

        for(let i = startIndex;i<= n;i++){
            arr.push(i)
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(1)

    return result

};
为什么循环调用的是backtracking(i+1) 而不是 backtracking(startIndex+1)

backtracking(i + 1)的含义是：

  • 我现在选了数字 i
  • 下一层应该从 i + 1 开始（即不能再选当前的 i 了，避免重复）

这相当于说：

每次递归往下传的是“我刚刚选了谁，接下来只能选比它更大的数字”。

backtracking(startIndex + 1)的意思是：

  • 不管我当前选了谁，我下一轮都从 startIndex + 1 开始选

问题就来了：

  • i 和 startIndex 可能是不一样的！
  • 如果你在循环里枚举了 i，就必须传 i + 1，不然会跳过一部分情况，或重复访问某些数字。

记住：

在回溯算法中：

  • 如果你在 for 循环里枚举的是 i
  • 那么递归就要 backtracking(i + 1)，才能正确推进枚举范围

注意点：

  • 不能直接result.push(arr)，要使用浅拷贝保存当前组件result.push([...arr])
  • 递归调用的是backtracking(i+1)，如果使用i会导致重复使用相同的数字，无法确保组合中数字是递增且不重复的

剪枝优化​

当 arr.length + (n - i + 1) < k 时，就不可能凑够 k 个数了，可以跳过。

所以我们可以限制i的最大范围：i <= n - (k - arr.length) + 1

var combine = function(n, k) {
    
    const arr = []
    const result = []

    function backtracking(startIndex){
        if(arr.length === k){
            result.push([...arr])
            return
        }

        for(let i = startIndex;i <= n - (k - arr.length) + 1;i++){
            arr.push(i)
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(1)

    return result

};

解释剪枝条件：

如果当前已经选了 arr.length 个数，还差 k - arr.length 个，那么：

  • 最后一个可能的起始数字是：n - (k - arr.length) + 1
  • 再往后的 i 都无法凑够剩下的组合，直接跳过。

组合总和III​

https://programmercarl.com/0216.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CIII.html

https://leetcode.cn/problems/combination-sum-iii/description/

思路​

与组件是一个思路

未剪枝​

var combinationSum3 = function(k, n) {
    const result = []
    let arr = []

    function backtracking(startIndex){
        if( arr.length === k &&  [...arr].reduce((sum, num) => sum + num, 0) === n ){
            result.push([...arr])
            return
        }

        for(let i = startIndex;i<= 9;i++){
            arr.push(i)
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(1)

    return result
};

剪枝​

var combinationSum3 = function(k, n) {
    const result = []
    let arr = []
    let sum = 0

    function backtracking(startIndex){
        if(sum > n) return

        if( arr.length === k &&  sum === n ){
            result.push([...arr])
            return
        }

        for(let i = startIndex;i <= 9 - (k - arr.length) + 1;i++){
            arr.push(i)
            sum += i
            backtracking(i+1)
            arr.pop()
            sum -= i
        }
    }

    backtracking(1)

    return result
};

电话号码的组合​

https://programmercarl.com/0017.%E7%94%B5%E8%AF%9D%E5%8F%B7%E7%A0%81%E7%9A%84%E5%AD%97%E6%AF%8D%E7%BB%84%E5%90%88.html

https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/

思路​

代码​

/**
 * @param {string} digits
 * @return {string[]}
 */
var letterCombinations = function(digits) {
    if (digits.length === 0) return []

    const arr1 = [
        [],
        [],
        ["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"],
    ]

    const arr2 = digits.split("").map(item => Number(item))

    const result = []
    let arr = []

    function backtracking(index){
        // index就是用来遍历digits
        if( index === arr2.length ){
            result.push([...arr].join(""))

            return
        }

        const arr3 = arr1[arr2[index]]

        for(let i = 0;i < arr3.length; i++){
            arr.push(arr3[i])
            backtracking(index+1)
            arr.pop()
        }
    }

    backtracking(0)

    return result
};

组合总和​

https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html

https://leetcode.cn/problems/combination-sum/description/

思路​

注意自身是可以重复选择的，在循环调用的过程中注意参数

代码​

var combinationSum = function(candidates, target) {
    const result = []
    let sum = 0
    let arr = []

    function backtracking(index){
        if (sum > target || arr.length > 150) return

        if(arr.length <= 150 && sum === target){
            result.push([...arr])
            return
        }

        for(let i = index;i < candidates.length; i++){
            arr.push(candidates[i])
            sum += candidates[i]
            backtracking(i)
            const a = arr.pop()
            sum -= a
        }
    }

    backtracking(0)

    return result
};

注意：涉及到和，就有和大于对比值的情况，需要去除掉

组合总和II​

https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html

https://leetcode.cn/problems/combination-sum-ii/description/

思路​

先排序

代码​

var combinationSum2 = function(candidates, target) {
    candidates.sort((a, b) => a - b)

    const result = []
    let sum = 0
    let arr = []

    function backtracking(index){
        if (sum > target) return

        if(sum === target){
            result.push([...arr])
            return
        }

        for(let i = index;i < candidates.length; i++){
            if(i > index && candidates[i] === candidates[i-1] ) continue 
            arr.push(candidates[i])
            sum += candidates[i]
            backtracking(i+1)
            const a = arr.pop()
            sum -= a
        }
    }

    backtracking(0)

    return result
};
为什么是candidates[i] === candidates[i-1]进行continue

关键区别不在“值”，而在树的层级（递归路径）

我们并不是跳过所有的重复值，而是只跳过“在同一递归层级中的重复值”。

我们允许：

  • 不同递归层中的重复值 ✅
  • 同一层中的重复值 ❌（因为会导致重复组合）

举个例子：candidates = [1, 1, 2]，target = 3

我们展开递归树（简化为只显示值）：

Level 0: []
  ├── Level 1: [1]    // i = 0
  │     ├── [1,1]     // i = 1
  │     │     └── [1,1,2] -> 超出
  │     └── [1,2] ✅  // i = 2
  └── Level 1: [1] ❌ // i = 1 ←⚠️ 重复了第一条路径的组合
        └── [1,2] ← 重复路径

所以判断：if (i > start && candidates[i] === candidates[i - 1])

它的意思是：

  • i > start：说明我们正在当前递归的“同一层级”中横向遍历
  • candidates[i] === candidates[i - 1]：两个值相同
  • 那就跳过当前这个 candidates[i]，因为你已经在这一层用过一次相同的值了，再用就是重复组合。

分割回文串​

https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html

https://leetcode.cn/problems/palindrome-partitioning/description/

思路​

代码​

var partition = function(s) {
    let result = []
    let arr = []

    function backtracking(startIndex){
        if(startIndex === s.length){
            result.push([...arr])
            return
        }

        for(let i = startIndex;i < s.length;i++){
            if(!isH(s, startIndex, i)) continue
            arr.push(s.slice(startIndex, i + 1))
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(0)

    return result
};

function isH(str, start, end){
    for(let i = start, j = end; i < j;i++,j--){
        if(str[i] !== str[j]){
            return false
        }
    }

    return true
}
为什么循环结束条件是startIndex === s.length

当 index === s.length，说明已经处理完了整个字符串，到达了叶子节点，当前路径 arr 中保存的是一种合法的回文划分结果，可以加入结果集了。

复原IP地址​

https://programmercarl.com/0093.%E5%A4%8D%E5%8E%9FIP%E5%9C%B0%E5%9D%80.html

https://leetcode.cn/problems/restore-ip-addresses/description/

思路​

与分割回文串的思路差不多

代码​

var restoreIpAddresses = function(s) {
    const result = []
    const arr = []

    function backtracking(startIndex){
        if (arr.length > 4) return
        if(startIndex === s.length && arr.length === 4){
            result.push([...arr].join("."))
        }

        for(let i = startIndex;i < s.length;i++){
        // 这里可以优化一下：
        // for(let i = startIndex; i < s.length && i < startIndex + 3; i++)，最长切3位
            if(!isIP(s, startIndex, i)) continue
            arr.push(s.slice(startIndex, i + 1))
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(0)

    return result
};

function isIP(str, start, end){
    const s = str.slice(start, end + 1)

    if(s.length === 0 || s.length > 3) return false
    if(s.length > 1 && s[0] === "0") return false // 不能以0开头
    const num = Number(s)
    return num >= 0 && num <= 255
}

子集​

https://programmercarl.com/0078.%E5%AD%90%E9%9B%86.html

https://leetcode.cn/problems/subsets/description/

思路​

如果把 子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！

代码​

var subsets = function(nums) {
    const result = []
    const arr = []

    function backtracking(startIndex){
        result.push([...arr])

        for(let i = startIndex;i<nums.length;i++){
            arr.push(nums[i])
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(0)
    return result
};
result.push([...arr])怎么没有条件限制

这是因为「子集问题」的目标是 列出所有可能的组合（包含空集），所以每一个路径状态都算一个子集

注意：当我们收集的是每一个节点而不是叶子节点的时候，是不需要return的

子集II​

https://programmercarl.com/0090.%E5%AD%90%E9%9B%86II.html

https://leetcode.cn/problems/subsets-ii/description/

思路​

与组合总和II的思路差不多，去掉重复的即可

代码​

var subsetsWithDup = function(nums) {
    nums.sort((a, b) => a - b)
    const result = []
    const arr = []

    function backtracking(startIndex){
        result.push([...arr])

        for(let i = startIndex; i < nums.length; i++){
            if(i > startIndex && nums[i] === nums[i-1]) continue
            arr.push(nums[i])
            backtracking(i+1)
            arr.pop()
        }
    }

    backtracking(0)

    return result
};

递增子序列​

https://programmercarl.com/0491.%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97.html

https://leetcode.cn/problems/non-decreasing-subsequences/description/

思路​

代码​

var findSubsequences = function (nums) {
    const result = []
    const res = []

    function backtracking(startIndex) {
        if (res.length >= 2) {
            result.push([...res])
        }

        // 同一层，一个数据只能用一次
        const set = new Set()
        for (let i = startIndex; i < nums.length; i++) {
            if (res.length > 0 && nums[i] < res[res.length - 1]) continue

            if (set.has(nums[i])) continue

            res.push(nums[i])
            set.add(nums[i])

            backtracking(i + 1)
            res.pop()
        }
    }

    backtracking(0)

    return result
};

::: if (res.length > 0 && nums[i] < res[res.length - 1]) continue 与 if (i > startIndex && nums[i] < res[res.length - 1]) continue 区别

它们看起来很相似，但含义和作用是不同的，下面我们来逐一讲清楚它们的区别。

✅ 第一种：if (res.length > 0 && nums[i] < res[res.length - 1])

✅ 作用：用于判断当前选的数是否满足递增条件

🌟 重点：这是逻辑判断，不管递归到了哪一层、索引是多少，只要不递增就跳过。

✅ 适用于：任何需要构造递增子序列的回溯场景

第二种：if (i > startIndex && nums[i] < res[res.length - 1])

⚠️ 作用：其实没有实际意义，容易混淆逻辑

❌ 问题：

  • i > startIndex 是用于剪枝去重的条件（搭配 nums[i] === nums[i-1] 才有意义）。
  • 但你这里配的是 nums[i] < res[res.length - 1]，这不是剪枝条件，而是递增性判断。

❗混用了剪枝前提条件和递增判断条件，导致逻辑容易错误。

:::

全排列​

https://programmercarl.com/0046.%E5%85%A8%E6%8E%92%E5%88%97.html

https://leetcode.cn/problems/permutations/description/

思路​

排列问题：

  • 每层都是从0开始搜索而不是startIndex
  • 需要used数组记录path里都放了哪些元素了

代码​

var permute = function(nums) {
    const result = []

    const res = []

    function backtracking(index){
        if(res.length === nums.length){
            result.push([...res])
            return
        }

        for(let i = 0;i<nums.length;i++){
            if(res.includes(nums[i])) continue
            res.push(nums[i])
            backtracking(i+1)
            res.pop()
        }
    }

    backtracking(0)

    return result
};
// 使用includes方法在大数据的查询下效率较低，可以使用标记数组 + 回溯
var permute = function(nums) {
    const result = []
    const path = []
    const used = new Array(nums.length).fill(false)

    function backtrack() {
        if (path.length === nums.length) {
            result.push([...path])
            return
        }

        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue
            path.push(nums[i])
            used[i] = true
            backtrack()
            path.pop()
            used[i] = false
        }
    }

    backtrack()
    return result
};

全排列II​

https://programmercarl.com/0047.%E5%85%A8%E6%8E%92%E5%88%97II.html

https://leetcode.cn/problems/permutations-ii/description/

思路​

排序+去重

代码​

var permuteUnique = function(nums) {
    nums.sort((a, b) => a - b)
    const result = []
    const res = []
    const used = new Array(nums.length).fill(false)

    function backtracking(index){
        if(res.length === nums.length){
            result.push([...res])
            return
        }

        for(let i =0;i<nums.length;i++){
            if(used[i]) continue
            if( i > 0 && nums[i] === nums[i-1] && !used[i - 1] ) continue
            res.push(nums[i])
            used[i] = true
            backtracking(i+1)
            res.pop()
            used[i] = false
        }
    }


    backtracking(0)

    return result
};
为什么需要&& !used[i - 1]

因为我们希望“相同元素只能在前一个相同元素被使用的情况下才能使用”，这样才能避免排列重复。

N皇后​

https://programmercarl.com/0051.N%E7%9A%87%E5%90%8E.html

https://leetcode.cn/problems/n-queens/description/

思路​

代码​

var solveNQueens = function(n) {
    const result = []
    const res = new Array(n).fill(".").map(() => new Array(n).fill("."));

    function backtracking(row){
        if(row === n){
            const copy = res.map(item => item.join(""))
            result.push(copy)
            return
        }

        for(let i = 0;i<n;i++){
            // 判断N皇后是否合法
            if(isQ()){
                res[row][i] = "Q"
                backtracking(row+1)
                res[row][i] = "."
            }
        }
    }

    backtracking(0)

    return result
};
// 下面就是如何判断是否合法的方法了：
// 上下左右斜着都不能有
function isQ(res, row, x, n){
    // 不需要检查同一行
    // 检查同一列
    for(let i = 0; i< row;i++){
        if(res[i][x] === "Q") return false
    }

    // 检查左上45°角
    for(let i = row - 1, j = x - 1;i >= 0 && x >= 0;i--, j--){
        if (res[i][j] === "Q") return false
    }

    // 检查右上45°角
    for(let i = row - 1, j = x + 1; i >=0 && j < n ;i--,j++ ){
        if (res[i][j] === "Q") return false
    }

    return true
}
// 完整代码
var solveNQueens = function (n) {
    const result = []
    const res = new Array(n).fill(".").map(() => new Array(n).fill("."));

    function backtracking(row) {
        if (row === n) {
            const copy = res.map(item => item.join(""))
            result.push(copy)
            return
        }

        for (let i = 0; i < n; i++) {
            if (!isQ(res, row, i, n)) continue
            res[row][i] = "Q"
            backtracking(row + 1)
            res[row][i] = "."
        }
    }

    backtracking(0)

    return result
};


function isQ(res, row, x, n) {
    // 不需要检查同一行
    // 检查同一列
    for (let i = 0; i < row; i++) {
        if (res[i][x] === "Q") return false
    }

    // 检查左上45°角
    for (let i = row - 1, j = x - 1; i >= 0 && x >= 0; i--, j--) {
        if (res[i][j] === "Q") return false
    }

    // 检查右上45°角
    for (let i = row - 1, j = x + 1; i >= 0 && j < n; i--, j++) {
        if (res[i][j] === "Q") return false
    }

    return true
}
为什么只检查“列”和“对角线”，不检查行？

原因：每一行只放一个皇后！

N 皇后问题的回溯策略是：一行一行往下放皇后，也就是说：

  • 第 0 行放一个皇后
  • 第 1 行再放一个皇后
  • ...
  • 第 N-1 行放完就完成了

这意味着：

在同一时间，某一行只可能有一个皇后。

总结​

回溯是递归的副产品，只要有递归就会有回溯，所以回溯法也经常和二叉树遍历，深度优先搜索混在一起，因为这两种方式都是用了递归。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解决如下问题：

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