常见的回溯模板题目

回溯算法解题框架

解决一个回溯问题，需要考虑以下三个问题:

• 路径：也就是已经做出的选择
• 选择列表：当前能做的选择
• 结束条件：达到决策树的底层无法在做出选择

代码框架：

result = []
def backtrap(路径，选择列表):
  if 满足结束条件:
    result.add(路径)
    return
  for 选择 in 选择列表:
    做选择
    backtrap(路径,选择列表)
    撤销选择

核心其实就是for循环里面的递归，在递归调用之前“做出一个选择”，在递归调用之后”撤销选择“。

通过题目来做一些理解吧

明人不说暗话，直接上全排列:

lc46

题目链接：https://leetcode-cn.com/problems/permutations/

这题就是一个很典型的回溯板子

因为这里我们需要撤销一下之前的走过的选项，所以就需要递归前选元素，递归之后再撤销刚才的选择。

直接看一波代码吧：

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
  let res = []
  let temp = []
  const dfs = (temp, nums) => {
      if (temp.length === nums.length) {
          res.push([...temp])
          return;
      }
      for (let item of nums) {
          if(temp.includes(item)) {
              continue;
          }
          // 做出选择
          temp.push(item)
          // 回溯一波
          dfs(temp, nums)
          // 回溯走完之后把选择的元素pop走
          temp.pop()
      }
  }
  dfs([], nums)
  return res;
};

lc784

题目链接:https://leetcode-cn.com/problems/letter-case-permutation/

这题其实也是个回溯。

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
/**
 * @param {string} S
 * @return {string[]}
 */
var letterCasePermutation = function(S) {
   let res = []
   S = S.split('')
   let temp = []
   const dfs = (temp, S,index) => {
       if(index === S.length) {
           res.push(S.join(''))
           return;
       }
       // 如果当前字符是英文字母，那么就进行一波回溯操作
       if(('A' <=S[index]&& S[index] <= 'Z') || ('a' <= S[index] && S[index] <='z')) {
           S[index] = S[index].toLowerCase()
           dfs(temp, S, index + 1)
           S[index] = S[index].toUpperCase()
           dfs(temp, S, index + 1)
       } else {
           // 如果是数字，直接去递归就好了
           dfs(temp, S, index + 1)
       }
   }
   dfs(temp, S, 0)
   return res;
};

lc51 n皇后问题

题目链接:https://leetcode-cn.com/problems/n-queens/

规则:有个 N * N 的棋盘，让你放置 N 个皇后，使他们不能互相攻击。

PS: 攻击的规则是皇后可以攻击同一行、同一列、左上左下右上右下四个方向的任意单位。

这个问题本质上是和全排列差不多的，决策树的每一层表示棋盘上的每一行;每个节点都可以做出的选择是，在该行的任意一列放置一个皇后:

先写一波伪代码:

const res = []

const solve = (n) => {
  // . 表示空盘，Q表示皇后，初始化空棋盘
  for (let i = 0;i<n;i++) {
    for (let j = 0;j<n;j++) {
      board[i][j] = '.'
    }
  }
  const backtrap = (board, row) => {
    // 触发结束条件
    if (row === board.length) {
      res.push(board)
      return
    }
    let n = board[row].length
    for (let col = 0; col < n; col++) {
      // 不符合规定的选择直接pass掉
      if (!isValid(board, row, col)) {
        continue;
      }
      // 做出选择
      board[row][col] = 'Q'
      // 进入下一行决策
      backtrap(board, row + 1)
      // 撤销掉之前的选择
      board[row][col] = '.'
    }
  }
  backtrap(board, 0);
  return res;
}

主要部分的代码其实和全排列差不多，isValid函数的实现为:

const isvalid = (board, row, col) => {
  let n = board.length
  // 检查当前列是否有皇后
  for(let i = 0;i<n;i++) {
    if(board[i][col] === 'Q') {
      return false;
    }
  }
  // 检查右上是否有皇后
  for (let i = row - 1,j = col + 1;i>=0 && j<n;i--;j++) {
    if(board[i][j] === 'Q') {
      return false;
    }
  }
  // 检查左上是否有皇后
  for (let i = row - 1,j=col - 1;i>=0 && j>=0;i--,j--) {
    if(board[i][j] === 'Q') {
      return false
    }
  }
  return true
}

lc 水域大小

这题其实是个典型的dfs找联通块的题目，有8个方向:

/**
 * @param {number[][]} land
 * @return {number[]}
 */
var pondSizes = function (grid) {
  let m = grid.length
  if (m === 0) {
    return 0
  }
  let n = grid[0].length
  let res = -1
  const dfs = (grid, i, j, res) => {
    if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] !== 0) {
      return
    }
    grid[i][j] = res
    dfs(grid, i + 1, j, res)
    dfs(grid, i - 1, j, res)
    dfs(grid, i + 1, j + 1, res)
    dfs(grid, i + 1, j - 1, res)
    dfs(grid, i - 1, j + 1, res)
    dfs(grid, i - 1, j - 1, res)
    dfs(grid, i, j + 1, res)
    dfs(grid, i, j - 1, res)
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 0) {
        dfs(grid, i, j, res--)
      }
    }
  }
  let hash = new Map()
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] < 0) {
        hash.set(grid[i][j], hash.has(grid[i][j]) ? hash.get(grid[i][j]) + 1 : 1)
      }
    }
  }
  let ret = []
  for (let [key, value] of hash) {
    ret.push(value)
  }
  return ret.sort((a, b) => a - b)
}

// console.log(
//   pondSizes([
//     [0, 2, 1, 0],
//     [0, 1, 0, 1],
//     [1, 1, 0, 1],
//     [0, 1, 0, 1],
//   ]),
// )