当前位置：首页 > JavaScript

js实现回溯

2026-04-05 21:42:16JavaScript

回溯算法的基本概念

回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解（或者至少不是最后一个解），回溯算法会放弃该解，回退到上一步，尝试其他的可能性。回溯算法通常用递归来实现。

回溯算法的适用场景

回溯算法常用于解决组合问题、排列问题、子集问题、棋盘问题等。例如，八皇后问题、数独、全排列、组合总和等问题都可以用回溯算法解决。

回溯算法的框架

回溯算法的基本框架可以总结为以下几步：

js实现回溯

选择路径：从可选的选项中做出一个选择。
递归探索：基于当前选择，继续递归地探索下一步的选择。
撤销选择：在递归返回后，撤销当前的选择，以便尝试其他选项。

回溯算法的代码实现

以下是一个通用的回溯算法框架：

function backtrack(路径, 选择列表) {
    if (满足结束条件) {
        结果.push(路径);
        return;
    }

    for (选择 of 选择列表) {
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;
    }
}

示例：全排列问题

全排列问题是一个经典的回溯算法应用。给定一个不重复的数字序列，返回所有可能的全排列。

js实现回溯

function permute(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);

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

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

    backtrack([]);
    return result;
}

console.log(permute([1, 2, 3]));

示例：组合总和问题

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

function combinationSum(candidates, target) {
    const result = [];

    function backtrack(start, path, remaining) {
        if (remaining === 0) {
            result.push([...path]);
            return;
        }

        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) continue;
            path.push(candidates[i]);
            backtrack(i, path, remaining - candidates[i]);
            path.pop();
        }
    }

    backtrack(0, [], target);
    return result;
}

console.log(combinationSum([2, 3, 6, 7], 7));

回溯算法的优化

回溯算法的时间复杂度通常较高，因为它需要探索所有可能的解。可以通过剪枝来优化回溯算法的性能。剪枝是指在递归过程中提前终止那些不可能产生解的路径。

剪枝示例

在组合总和问题中，可以通过排序和提前终止来优化：

function combinationSum(candidates, target) {
    const result = [];
    candidates.sort((a, b) => a - b);

    function backtrack(start, path, remaining) {
        if (remaining === 0) {
            result.push([...path]);
            return;
        }

        for (let i = start; i < candidates.length; i++) {
            if (candidates[i] > remaining) break;
            path.push(candidates[i]);
            backtrack(i, path, remaining - candidates[i]);
            path.pop();
        }
    }

    backtrack(0, [], target);
    return result;
}

console.log(combinationSum([2, 3, 6, 7], 7));