当前位置：首页 > JavaScript

js实现回溯

2026-03-14 03:36:05JavaScript

回溯算法的基本概念

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会放弃该解，回退到上一步，尝试其他的可能性。回溯算法通常用于解决组合问题、排列问题、子集问题等。

回溯算法的框架

回溯算法通常通过递归实现，其核心框架如下：

选择路径：在当前步骤选择一个候选解。
递归探索：基于当前选择，继续递归探索下一步。
撤销选择：如果当前路径无法达到解，撤销选择，回退到上一步。

回溯算法的实现示例

以下是几个经典的回溯算法问题的JavaScript实现。

全排列问题

给定一个不含重复数字的数组，返回其所有可能的全排列。

function permute(nums) {
    const result = [];
    backtrack(nums, [], result);
    return result;
}

function backtrack(nums, path, result) {
    if (path.length === nums.length) {
        result.push([...path]);
        return;
    }
    for (let i = 0; i < nums.length; i++) {
        if (path.includes(nums[i])) continue;
        path.push(nums[i]);
        backtrack(nums, path, result);
        path.pop();
    }
}

子集问题

给定一个不含重复元素的整数数组，返回其所有可能的子集。

function subsets(nums) {
    const result = [];
    backtrack(nums, 0, [], result);
    return result;
}

function backtrack(nums, start, path, result) {
    result.push([...path]);
    for (let i = start; i < nums.length; i++) {
        path.push(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.pop();
    }
}

组合总和问题

给定一个无重复元素的数组和一个目标数，找出所有可以使数字和为目标数的组合。

function combinationSum(candidates, target) {
    const result = [];
    backtrack(candidates, target, 0, [], result);
    return result;
}

function backtrack(candidates, target, start, path, result) {
    if (target < 0) return;
    if (target === 0) {
        result.push([...path]);
        return;
    }
    for (let i = start; i < candidates.length; i++) {
        path.push(candidates[i]);
        backtrack(candidates, target - candidates[i], i, path, result);
        path.pop();
    }
}

回溯算法的优化

回溯算法的时间复杂度通常较高，可以通过剪枝优化性能。例如在组合总和问题中，如果数组是排序的，可以在递归前判断剩余目标是否小于当前数字，从而提前终止不必要的递归。

js实现回溯

function combinationSum(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b); // 排序
    backtrack(candidates, target, 0, [], result);
    return result;
}

function backtrack(candidates, target, start, path, result) {
    if (target === 0) {
        result.push([...path]);
        return;
    }
    for (let i = start; i < candidates.length; i++) {
        if (candidates[i] > target) break; // 剪枝
        path.push(candidates[i]);
        backtrack(candidates, target - candidates[i], i, path, result);
        path.pop();
    }
}