当前位置：首页 > JavaScript

js实现回溯

2026-02-01 05:17:11JavaScript

回溯算法的基本概念

回溯算法是一种通过递归尝试所有可能解并在不满足条件时回退（回溯）的算法。常用于解决组合、排列、子集、棋盘类问题（如八皇后、数独）等。

回溯算法的框架

回溯通常通过递归实现，核心步骤如下：

选择路径：在当前步骤选择一个候选解（例如选择一个数字填入排列）。
递归探索：基于当前选择进入下一层递归。
撤销选择：如果发现当前选择无法达到最终解，则回溯到上一步（撤销选择）。

通用代码框架如下：

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; // 跳过已使用的数字
      used[i] = true;
      path.push(nums[i]);
      backtrack(path, used);
      path.pop(); // 回溯
      used[i] = false;
    }
  };
  backtrack([], new Array(nums.length).fill(false));
  return res;
}
// 示例：permute([1,2,3]) 输出 [[1,2,3], [1,3,2], ...]

示例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); // 避免重复，从i+1开始
      path.pop(); // 回溯
    }
  };
  backtrack(0, []);
  return res;
}
// 示例：subsets([1,2,3]) 输出 [[], [1], [1,2], ...]

示例3：N皇后问题

在N×N棋盘上放置皇后，使其互不攻击。

function solveNQueens(n) {
  const res = [];
  const board = new Array(n).fill().map(() => new Array(n).fill('.'));

  const isValid = (row, col) => {
    // 检查列是否有冲突
    for (let i = 0; i < row; i++) {
      if (board[i][col] === 'Q') return false;
    }
    // 检查左上方对角线
    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
      if (board[i][j] === 'Q') return false;
    }
    // 检查右上方对角线
    for (let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
      if (board[i][j] === 'Q') return false;
    }
    return true;
  };

  const backtrack = (row) => {
    if (row === n) {
      res.push(board.map(row => row.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (!isValid(row, col)) continue;
      board[row][col] = 'Q';
      backtrack(row + 1);
      board[row][col] = '.'; // 回溯
    }
  };
  backtrack(0);
  return res;
}
// 示例：solveNQueens(4) 输出 [["..Q.", "Q...", "...Q", ".Q.."], [...]]

关键点

剪枝优化：通过条件判断提前终止无效分支（如isValid函数）。
路径记录：使用数组或栈保存当前路径，回溯时需撤销修改。
去重处理：若问题允许重复元素，需排序后跳过相同值（如if (i > start && nums[i] === nums[i-1]) continue）。

js实现回溯