【JavaScript 算法】回溯法：解决组合与排列问题

空白诗

发布于 2024-07-20 12:39:25

550

发布于 2024-07-20 12:39:25

文章被收录于专栏：【全栈开发之路】

回溯法是一种通过尝试所有可能的解来解决问题的算法策略。它在组合和排列问题中尤为有效，通过递归地构建解空间树并在必要时进行回退（即“回溯”），从而找到所有满足条件的解。

一、回溯法的基本概念

回溯法的基本思想是构建一个解的空间树，通过深度优先搜索来遍历所有可能的解。在遍历的过程中，如果发现当前部分解不能构成最终解，就回溯到上一步继续尝试其他可能的解。这种方法特别适用于组合、排列、子集等问题。

回溯法的模板

回溯法的一般模板如下：

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

二、经典问题及其 JavaScript 实现

1. 组合问题

假设我们要从 [1, 2, 3, 4] 中选择 2 个数字的所有组合。

问题描述：从给定数组中选择 k 个元素的所有组合。

/**
 * 求数组中所有长度为 k 的组合
 * @param {number[]} nums - 输入数组
 * @param {number} k - 组合的长度
 * @returns {number[][]} - 所有组合的数组
 */
function combine(nums, k) {
    const result = [];
    
    /**
     * 回溯函数
     * @param {number} start - 起始索引
     * @param {number[]} path - 当前路径
     */
    function backtrack(start, path) {
        // 如果路径长度等于 k，加入结果
        if (path.length === k) {
            result.push([...path]);
            return;
        }
        // 遍历选择列表
        for (let i = start; i < nums.length; i++) {
            // 做选择
            path.push(nums[i]);
            // 递归调用
            backtrack(i + 1, path);
            // 撤销选择
            path.pop();
        }
    }
    
    // 从第一个元素开始回溯
    backtrack(0, []);
    return result;
}

// 示例：求 [1, 2, 3, 4] 中所有长度为 2 的组合
console.log(combine([1, 2, 3, 4], 2));
// 输出：[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

2. 排列问题

假设我们要求 [1, 2, 3] 的所有排列。

问题描述：求给定数组的所有排列。

/**
 * 求数组的所有排列
 * @param {number[]} nums - 输入数组
 * @returns {number[][]} - 所有排列的数组
 */
function permute(nums) {
    const result = [];
    
    /**
     * 回溯函数
     * @param {number[]} path - 当前路径
     * @param {Set} used - 已使用的元素集合
     */
    function backtrack(path, used) {
        // 如果路径长度等于 nums 长度，加入结果
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        // 遍历选择列表
        for (let i = 0; i < nums.length; i++) {
            if (used.has(nums[i])) continue;
            // 做选择
            path.push(nums[i]);
            used.add(nums[i]);
            // 递归调用
            backtrack(path, used);
            // 撤销选择
            path.pop();
            used.delete(nums[i]);
        }
    }
    
    // 从空路径和空集合开始回溯
    backtrack([], new Set());
    return result;
}

// 示例：求 [1, 2, 3] 的所有排列
console.log(permute([1, 2, 3]));
// 输出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]