当前位置：首页 > JavaScript

js实现回溯法

2026-02-03 00:28:20JavaScript

回溯法概述

回溯法是一种通过递归或迭代探索所有可能解的算法，常用于解决组合、排列、子集等问题。其核心思想是“试错”：尝试某条路径，若发现不满足条件则回退（回溯），尝试其他路径。

回溯法的基本结构

回溯法通常包含以下步骤：

选择路径：从可选选项中做出一个选择。
递归探索：基于当前选择继续向下探索。
撤销选择：若当前路径不满足条件，回退到上一步状态。

通用代码框架：

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

经典问题示例

1. 全排列问题

给定不重复数字数组，返回所有可能的排列。

function permute(nums) {
    const res = [];
    const backtrack = (path, used) => {
        if (path.length === nums.length) {
            res.push([...path]);
            return;
        }
        for (let i = 0; i < nums.length; i++) {
            if (used[i]) continue;
            path.push(nums[i]);
            used[i] = true;
            backtrack(path, used);
            path.pop();
            used[i] = false;
        }
    };
    backtrack([], new Array(nums.length).fill(false));
    return res;
}

2. 子集问题

返回数组所有可能的子集。

function subsets(nums) {
    const res = [];
    const backtrack = (start, path) => {
        res.push([...path]);
        for (let i = start; i < nums.length; i++) {
            path.push(nums[i]);
            backtrack(i + 1, path);
            path.pop();
        }
    };
    backtrack(0, []);
    return res;
}

3. 组合总和

找出数组中总和为目标的组合（可重复使用数字）。

function combinationSum(candidates, target) {
    const res = [];
    const backtrack = (start, path, sum) => {
        if (sum === target) {
            res.push([...path]);
            return;
        }
        if (sum > target) return;
        for (let i = start; i < candidates.length; i++) {
            path.push(candidates[i]);
            backtrack(i, path, sum + candidates[i]);
            path.pop();
        }
    };
    backtrack(0, [], 0);
    return res;
}