如何用JavaScript实现回溯算法？回溯算法原理与代码实例详解

回溯算法的核心思想是尝试分步去解决一个问题，当发现当前步骤不能得到有效解时，就回退到上一步重新选择其他路径，直到找到所有符合条件的解或者遍历完所有可能。在JavaScript中实现回溯算法，通常会结合递归来完成路径的遍历和回退操作。

回溯算法的通用框架

回溯算法的实现通常可以抽象为以下几个固定步骤，掌握这个框架后，大部分回溯类问题都可以按照这个思路来写代码：

• 定义路径：记录当前已经做出的选择
• 定义选择列表：记录当前可以做出的所有选择
• 结束条件：当路径满足问题要求的解时，将当前路径加入结果集
• 遍历选择列表：对每个可选选择，做选择、递归进入下一层、撤销选择（回退）

对应的通用伪代码如下：

// 结果集
const res = []
// 回溯主函数
function backtrack(路径, 选择列表) {
    // 满足结束条件
    if (满足结束条件) {
        res.push(路径的拷贝)
        return
    }
    for (选择 in 选择列表) {
        // 做选择
        路径.push(选择)
        // 递归进入下一层
        backtrack(路径, 新的选择列表)
        // 撤销选择，回退到上一步
        路径.pop()
    }
}

实例1：生成数组的全排列

全排列问题是回溯算法的经典应用场景，给定一个不含重复数字的数组，返回其所有可能的全排列。比如输入[1,2,3]，输出所有三个数字的排列组合。

实现思路：路径记录当前已经选择的数字，选择列表是还未被选择的数字，当路径长度等于原数组长度时，说明得到一个完整的排列，加入结果集。每次选择数字后，要将其从选择列表中移除，避免重复选择，递归结束后恢复选择列表。

function permute(nums) {
    const res = []
    const path = []
    const used = new Array(nums.length).fill(false) // 记录数字是否已被选择
    function backtrack() {
        // 结束条件：路径长度等于数组长度，说明得到一个全排列
        if (path.length === nums.length) {
            res.push([...path]) // 拷贝当前路径加入结果集
            return
        }
        for (let i = 0; i < nums.length; i++) {
            // 跳过已经选择过的数字
            if (used[i]) continue
            // 做选择
            used[i] = true
            path.push(nums[i])
            // 递归进入下一层
            backtrack()
            // 撤销选择，回退操作
            path.pop()
            used[i] = false
        }
    }
    backtrack()
    return res
}

// 测试代码
console.log(permute([1,2,3]))

实例2：生成数组的所有子集

子集问题要求给定一个整数数组，返回该数组所有可能的子集，解集不能包含重复的子集。比如输入[1,2,3]，输出[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]。

实现思路：每个元素都有选和不选两种状态，我们可以按顺序遍历数组，每次递归时可以选择当前元素加入路径，也可以选择不加入，当遍历完所有元素时，当前路径就是一个子集。为了避免重复子集，我们可以规定选择列表是后续还未遍历的元素，这样不会生成顺序不同但内容相同的子集。

function subsets(nums) {
    const res = []
    const path = []
    function backtrack(start) {
        // 每次进入递归都将当前路径加入结果集，因为空集和每个中间路径都是合法子集
        res.push([...path])
        for (let i = start; i < nums.length; i++) {
            // 做选择，加入当前元素
            path.push(nums[i])
            // 递归处理后续元素，start设为i+1，避免重复选择前面的元素
            backtrack(i + 1)
            // 撤销选择
            path.pop()
        }
    }
    backtrack(0)
    return res
}

// 测试代码
console.log(subsets([1,2,3]))

回溯算法的剪枝优化

在很多回溯问题中，我们会遇到一些明显不可能得到正确解的选择，这时候可以在遍历选择列表时提前跳过这些选择，减少不必要的递归，这个操作就是剪枝。比如在生成组合总和的问题中，如果当前路径的和已经超过了目标值，就不需要再继续添加元素了。

下面以组合总和问题为例，给定一个无重复元素的数组和一个目标数，找出数组中所有可以使数字和为目标数的组合，数组中的数字可以无限制重复被选取。实现时如果当前和已经超过目标值，就直接跳过后续选择：

function combinationSum(candidates, target) {
    const res = []
    const path = []
    // 先对数组排序，方便剪枝
    candidates.sort((a,b) => a - b)
    function backtrack(start, currentSum) {
        // 当前和等于目标值，得到合法组合
        if (currentSum === target) {
            res.push([...path])
            return
        }
        for (let i = start; i < candidates.length; i++) {
            // 剪枝：如果当前数字加上后已经超过目标值，后续更大的数字更会超过，直接跳出循环
            if (currentSum + candidates[i] > target) break
            // 做选择
            path.push(candidates[i])
            // 递归，因为数字可以重复选，所以start还是i
            backtrack(i, currentSum + candidates[i])
            // 撤销选择
            path.pop()
        }
    }
    backtrack(0, 0)
    return res
}

// 测试代码
console.log(combinationSum([2,3,6,7], 7))

回溯算法的注意事项

在JavaScript中实现回溯算法时，有几个容易出错的点需要注意：

• 将路径加入结果集时，一定要拷贝当前路径，不能直接push路径引用，否则后续路径修改会影响已经加入结果集的内容
• 撤销选择的操作要和做选择的操作对应，确保递归回退后状态恢复到上一步
• 剪枝操作要放在合适的位置，既不要漏掉合法解，也不要做多余的判断
• 如果问题涉及重复元素，需要额外增加去重逻辑，通常可以先排序，然后在遍历选择时跳过和前一个元素相同的选择

回溯算法的时间复杂度通常比较高，因为需要遍历所有可能的选择，所以在处理大规模数据时，要结合剪枝等优化手段减少不必要的计算。熟练掌握回溯的通用框架后，大部分回溯类问题都可以通过调整选择列表、结束条件和剪枝逻辑来快速实现。

JavaScript回溯算法递归算法实现剪枝修改时间：2026-06-30 12:39:35