JavaScript算法实现_回溯算法-js教程-PHP中文网

JavaScript算法实现_回溯算法

夜晨

发布： 2025-11-22 22:17:02

原创

638人浏览过

回溯算法通过递归尝试所有可能路径，结合“做选择”与“撤销选择”实现深度优先搜索。其核心在于状态维护与及时回退，适用于全排列、子集等组合问题。JavaScript中利用递归和数组操作可轻松实现，关键注意结束条件、路径拷贝及选择列表更新。典型模板包含路径、选择列表和结果收集，确保每一步可逆且不遗漏解。

javascript算法实现_回溯算法

回溯算法是一种通过尝试解决问题的所有可能路径来寻找所有（或部分）解的算法。当发现当前路径不能得到解时，就“回退”到上一步，尝试其他路径。这种思想在JavaScript中可以通过递归和状态重置轻松实现。

回溯算法的核心思想

回溯的本质是深度优先搜索（DFS），结合了试探与撤销操作：

从一个初始状态出发，逐步构建解
每一步都尝试所有可选的选择
如果某条路径无法继续，就撤销最近的选择，回到之前的状态重新尝试
直到找到所有可行解或满足条件为止

基本模板（JavaScript版）

以下是一个通用的回溯算法结构：

function backtrack(path, options, result) {
  // 满足结束条件
  if (满足条件) {
    result.push([...path]); // 注意：拷贝当前路径
    return;
  }

  for (let i = 0; i < options.length; i++) {
    // 做选择
    path.push(options[i]);

    // 进入下一层决策
    backtrack(path, 新的选择列表, result);

    // 撤销选择（回溯）
    path.pop();
  }
}

登录后复制

经典案例：全排列

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

立即学习“Java免费学习笔记（深入）”；

MD5校验和计算小程序（C）

C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。

查看详情

function permute(nums) {
  const result = [];

  function backtrack(path, used) {
    // 结束条件：路径长度等于原数组长度
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }

    for (let num of nums) {
      if (used.has(num)) continue;

      // 做选择
      path.push(num);
      used.add(num);

      // 进入下一层
      backtrack(path, used);

      // 撤销选择
      path.pop();
      used.delete(num);
    }
  }

  backtrack([], new Set());
  return result;
}

// 示例
console.log(permute([1, 2, 3]));
// 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

登录后复制

另一个例子：子集问题

给定一个整数数组，返回所有可能的子集（幂集）。

function subsets(nums) {
  const result = [];

  function backtrack(start, path) {
    // 每个节点都是有效解，直接加入
    result.push([...path]);

    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);           // 做选择
      backtrack(i + 1, path);       // 下一层从i+1开始避免重复
      path.pop();                   // 撤销选择
    }
  }

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

// 示例
console.log(subsets([1, 2, 3]));
// 输出: [[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]

登录后复制

回溯算法的关键在于理解“做选择”和“撤销选择”的对称性。使用递归自然地保存了调用栈中的状态，而手动维护的路径变量需要在递归前后保持一致。只要掌握这个模式，大多数组合、排列、枚举类问题都可以迎刃而解。

基本上就这些，核心是递归结构 + 状态维护 + 及时回退。写的时候多注意边界条件和数据拷贝即可。

以上就是JavaScript算法实现_回溯算法的详细内容，更多请关注php中文网其它相关文章！