1 篇博文含有标签「回溯算法」

回溯算法解题模板

2021年3月6日 · 阅读需 9 分钟

模板

var leetcodeXXX = function(nums) {
  let res = [];
  let track = [];

  function backtrack(start) {
    if (满足条件) {
      // 将当前所做的选择列表传入结果列表中
      res.push(track.slice());
      return;
    }
    for (
      let i = start /* 这里取0还是取start需要看具体情况 */;
      i < nums.length;
      i++
    ) {
      // 减枝操作
      // 判断哪些情况下可以跳过,这一步也可以放到子递归中去处理
      if (需要跳过) continue;

      // 做出选择
      track.push(nums[i]);
      // 拿着刚刚做出的选择看结果
      backtrack(i + 1);
      // 撤回刚刚做出的选择
      track.pop(nums[i]);
    }
  }
  // 启动回溯算法
  backtrack();
  return res;
};

理解

解决一个回溯问题，实际上就是一个决策树的遍历过程决策树必须包含问题的所有解只需要思考 3 个问题： 1、路径：也就是已经做出的选择。 2、选择列表：也就是你当前可以做的选择。 3、结束条件：也就是到达决策树底层，无法再做选择的条件。

回溯算法的一个特点，不像动态规划存在重叠子问题可以优化，回溯算法就是纯暴力穷举，复杂度一般都很高。某种程度上说，动态规划的暴力求解阶段就是回溯算法。只是有的问题具有重叠子问题性质，可以用 dp table 或者备忘录优化，将递归树大幅剪枝，这就变成了动态规划

真题

全排列

/*
 * @lc app=leetcode.cn id=46 lang=javascript
 *
 * [46] 全排列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let res = [];
  let track = [];
  function backtrack(chooses) {
    if (chooses.length === track.length) {
      res.push(track.slice());
      return;
    }
    for (let i = 0; i < chooses.length; i++) {
      if (track.includes(chooses[i])) continue;
      // 作出选择
      track.push(chooses[i]);

      backtrack(chooses);

      // 所做的选择反悔
      track.pop();
    }
  }
  backtrack(nums);
  return res;
};
// @lc code=end

组合

/*
 * @lc app=leetcode.cn id=77 lang=javascript
 *
 * [77] 组合
 */

// @lc code=start
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
var combine = function(n, k) {
  let res = [];
  let track = [];
  function backtrack(start) {
    if (track.length === k) {
      res.push(track.slice());
      return;
    }

    for (let i = start; i <= n; i++) {
      track.push(i);
      backtrack(i + 1);
      track.pop();
    }
  }
  backtrack(1);
  return res;
};
// @lc code=end

子集

/*
 * @lc app=leetcode.cn id=78 lang=javascript
 *
 * [78] 子集
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var subsets = function(nums) {
  let res = [],
    track = [];
  function backtrack(nums, start) {
    res.push(track.slice());
    for (let i = start; i < nums.length; i++) {
      track.push(nums[i]);
      backtrack(nums, i + 1, track);
      track.pop();
    }
  }
  backtrack(nums, 0);
  return res;
};

// @lc code=end

四数之和

/*
 * @lc app=leetcode.cn id=18 lang=javascript
 *
 * [18] 四数之和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[][]}
 */
// 回溯算法, 疯狂减枝
var fourSum = function(nums, target) {
  let res = [];
  let track = [];
  nums.sort((a, b) => a - b);
  if (
    nums.length &&
    (nums[nums.length - 1] * 4 < target || nums[0] * 4 > target)
  ) {
    return [];
  }

  function backtrack(start = 0, Sum) {
    if (Sum === target && track.length === 4) {
      res.push(track.slice());
      return;
    }
    if (track.length > 4) return;
    for (let i = start; i < nums.length; i++) {
      if (nums.length - i < 4 - track.length) continue;
      if (i > start && nums[i] === nums[i - 1]) continue;
      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[i + 1] > target
      )
        continue;

      if (
        i < nums.length - 1 &&
        Sum + nums[i] + (3 - track.length) * nums[nums.length - 1] < target
      )
        continue;

      track.push(nums[i]);
      backtrack(i + 1, Sum + nums[i]);
      track.pop(nums[i]);
    }
  }
  backtrack(0, 0);
  return res;
};
// @lc code=end

// console.log(fourSum([1, 0, -1, 0, -2, 2], 0));

括号生成

/*
 * @lc app=leetcode.cn id=22 lang=javascript
 *
 * [22] 括号生成
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
  let track = [];
  let res = [];
  /**
   * leftNum 剩余左括号数量
   * rightNum 剩余右括号数量
   */
  function backtrack(leftNum, rightNum) {
    // 合格的括号对满足以下条件
    // 1. 任意字串[0,...,i]，左括号数量都大于右括号数量
    // 2. 对于所有合法的括号对，左括号数都等于右括号数

    // 剩余左括号数大于剩余右括号数，说明字串的左括号数小于右括号数，不符合条件
    if (leftNum > rightNum) return;
    // 剩余左括号数或者剩余右括号数不足，不符合条件
    if (leftNum < 0 || rightNum < 0) return;
    // 经过第一个判断，左括号数量肯定大于等于右括号数量，如果剩余左右括号数都为0，说明就是合格的括号对
    if (leftNum === 0 && rightNum === 0) {
      res.push(track.join(""));
      return;
    }

    // 做选择
    track.push("(");
    backtrack(leftNum - 1, rightNum);
    // 回溯
    track.pop();

    // 做选择
    track.push(")");
    backtrack(leftNum, rightNum - 1);
    // 回溯
    track.pop();
  }

  // 剩余左右括号数各给n个
  backtrack(n, n);
  return res;
};
// @lc code=end

N 皇后

/*
 * @lc app=leetcode.cn id=51 lang=javascript
 *
 * [51] N 皇后
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[][]}
 */
var solveNQueens = function(n) {
  const getMatrix = (n, stuff = "") => {
    const res = [];
    for (let i = 0; i < n; i++) {
      const list = [];
      for (let j = 0; j < n; j++) {
        list.push(stuff);
      }
      res.push(list);
    }
    return res;
  };
  const res = [];
  const emptyBoard = getMatrix(n, ".");
  backtrack(emptyBoard, 0, res);
  return res;
};

function backtrack(matrix, row, res) {
  if (matrix.length === row) {
    res.push(matrix.map((item) => item.join("")));
    return;
  }

  const rowData = matrix[row];
  for (let col = 0; col < rowData.length; col++) {
    if (!isValid(matrix, row, col)) {
      continue;
    }
    rowData[col] = "Q";
    backtrack(matrix, row + 1, res);
    rowData[col] = ".";
  }
}

function isValid(matrix, row, col) {
  const size = matrix.length;
  for (let i = 0; i < size; i++) {
    if (
      matrix[i][col] === "Q" ||
      matrix[row][i] === "Q" ||
      matrix[i][row + col - i] === "Q" ||
      matrix[i][i + col - row] === "Q"
    )
      return false;
  }

  return true;
}
// @lc code=end

解数独

/*
 * @lc app=leetcode.cn id=37 lang=javascript
 *
 * [37] 解数独
 */

// @lc code=start
/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function(board) {
  const maxRow = 9,
    maxCol = 9;
  function isValid(i, j, ch) {
    for (let k = 0; k < 9; k++) {
      if (board[i][k] === ch) return false;
      if (board[k][j] === ch) return false;
      const chunkI = Math.floor(i / 3);
      const chunkJ = Math.floor(j / 3);
      const chunkIStart = chunkI * 3;
      const chunkJStart = chunkJ * 3;
      const iIndex = chunkIStart + Math.floor(k / 3);
      const jIndex = chunkJStart + (k % 3);
      if (board[iIndex][jIndex] === ch) return false;
    }
    return true;
  }

  function backtrack(i, j) {
    if (j === maxCol) {
      return backtrack(i + 1, 0);
    }
    if (i === maxRow) {
      return true;
    }

    if (board[i][j] !== ".") {
      return backtrack(i, j + 1);
    }

    for (let t = 1; t <= 9; t++) {
      const ch = String(t);
      if (!isValid(i, j, ch)) continue;
      board[i][j] = ch;

      if (backtrack(i, j + 1)) {
        return true;
      }
      board[i][j] = ".";
    }
    return false;
  }
  backtrack(0, 0);
};
// @lc code=end

let matrix = [
  ["5", "3", ".", ".", "7", ".", ".", ".", "."],
  ["6", ".", ".", "1", "9", "5", ".", ".", "."],
  [".", "9", "8", ".", ".", ".", ".", "6", "."],
  ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
  ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
  ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
  [".", "6", ".", ".", ".", ".", "2", "8", "."],
  [".", ".", ".", "4", "1", "9", ".", ".", "5"],
  [".", ".", ".", ".", "8", ".", ".", "7", "9"],
];
solveSudoku(matrix);
console.log(matrix);

目标和

/*
 * @lc app=leetcode.cn id=494 lang=javascript
 *
 * [494] 目标和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} S
 * @return {number}
 */
var findTargetSumWays = function(nums, S) {
  let res = 0;
  let count = 0;
  function backtrack(i) {
    if (i === nums.length) {
      if (res === S) {
        count++;
      }
      return;
    }
    res += nums[i];
    backtrack(i + 1);
    res -= nums[i];

    res -= nums[i];
    backtrack(i + 1);
    res += nums[i];
  }
  backtrack(0);
  return count;
};
// @lc code=end

模板​

理解​

真题​

全排列​

组合​

子集​

四数之和​

括号生成​

N 皇后​

解数独​

目标和​

模板

理解

真题

全排列

组合

子集

四数之和

括号生成

N 皇后

解数独

目标和