js实现回溯法

回溯法概述

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

回溯法的基本结构

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

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

通用代码框架：

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;
}

优化技巧

1. 剪枝：提前终止不符合条件的路径。例如在组合总和中，若当前和超过目标则直接返回。
2. 去重：对输入数组排序，并在回溯时跳过重复元素（如 if (i > start && nums[i] === nums[i-1]) continue）。
3. 记忆化：对于重叠子问题，缓存中间结果以减少重复计算。

注意事项

• 递归深度过大可能导致栈溢出，需注意问题规模。
• 在撤销选择时（如 path.pop()），需确保状态回退到上一步的准确值。