递归代码模板

递归代码模板

def recursion(level, param1, param2, ...):

  # recursion terminator
  if level > MAX_LEVEL:
    print_result
    return

  # process logic in current level
  process_data(level, data...)

  # drill down
  self.recursion(level + 1, p1, ...)

  # reverse the current level status if needed
  reverse_status(level)

回溯解题思路

1. 用 for 循环去枚举出所有的选择。

2. 做出一个选择。

3. 基于这个选择，继续往下选择（递归）。

4. 上面的递归结束了，撤销这个选择，进入 for 循环的下一次迭代。

括号生成

题目地址 (opens new window)

var generateParenthesis = function(n) {
  const res = [];

  const helper = (left, right, s) => {
    if (left === n && right === n) {
      res.push(s);
      return;
    }
    // 如果左括号数量不大于 n，可以放一个左括号
    if (left < n) {
      helper(left + 1, right, s + "(");
    }
    // 如果右括号数量小于左括号的数量，可以放一个右括号
    if (right < left) {
      helper(left, right + 1, s + ")");
    }
  };

  helper(0, 0, "");

  return res;
};

var generateParenthesis = function(n) {
  const res = [];

  const helper = (left, right, s) => {
    if (left === 0 && right === 0) {
      res.push(s);
      return;
    }
    if (left > 0) {
      helper(left - 1, right, s + "(");
    }
    if (right > left) {
      helper(left, right - 1, s + ")");
    }
  };

  helper(n, n, "");

  return res;
};

子集 ✅

题目地址 (opens new window)

// 回溯：每个元素都有“选择”和“不选择”两种情况
// 时间复杂度 O(n * 2^n)；空间复杂度 O(n)，不计算返回结果占用的空间
var subsets = function(nums) {
  // 保存所有子集
  const res = [];

  // i 表示当前准备处理的元素下标，arr 表示当前构建的子集
  const helper = (i, arr) => {
    // 所有元素都处理完成，得到一个完整子集
    if (i === nums.length) {
      // 必须保存副本，避免后续回溯修改 arr 时影响已经保存的结果
      res.push(arr.slice());
      return;
    }

    // 取当前的元素
    arr.push(nums[i]);
    helper(i + 1, arr);

    // 撤销选择，恢复到处理当前元素之前的状态
    arr.pop();

    // 不取当前的元素
    helper(i + 1, arr);
  };

  // 从下标 0 和空子集开始进行回溯
  helper(0, []);

  return res;
};

// 二进制枚举：用 mask 的第 i 位表示是否选择 nums[i]
// 时间复杂度 O(n * 2^n)；空间复杂度 O(n)，不计算返回结果占用的空间
var subsets = function(nums) {
  // 保存所有子集
  const res = [];
  const n = nums.length;

  // n 个元素共有 2^n 种选择状态，mask 从 0 枚举到 2^n - 1
  for (let mask = 0; mask < (1 << n); ++mask) {
    // 保存当前 mask 对应的子集
    const arr = [];

    // 从低位到高位检查 mask 的每个二进制位，每一位对应 nums 中同下标的元素
    for (let i = 0; i < n; ++i) {
      // 1 << i：生成一个只有第 i 位为 1、其他位都为 0 的数字
      // mask & (1 << i)：通过按位与检查 mask 的第 i 位是否为 1
      // 结果不为 0，说明第 i 位为 1，需要把 nums[i] 加入当前子集
      // 例如 mask = 5（二进制 101）、i = 2 时，101 & 100 = 100，因此选择 nums[2]
      if (mask & (1 << i)) {
        arr.push(nums[i]);
      }
    }

    // 当前子集已经构建完成，加入结果数组
    res.push(arr);
  }

  return res;
};

子集 II

题目地址 (opens new window)

var subsetsWithDup = function(nums) {
  const res = [];
  nums.sort();

  const helper = (start, arr) => {
    res.push(arr.slice());
    if (start === nums.length) {
      return;
    }
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i - 1] === nums[i]) {
        continue;
      }
      arr.push(nums[i]);
      helper(i + 1, arr);
      arr.pop();
    }
  };

  helper(0, []);

  return res;
};

组合

题目地址 (opens new window)

var combine = function(n, k) {
  const res = [];

  // start 是选择的起点，arr 是当前构建的组合
  const helper = (start, arr) => {
    if (arr.length === k) {
      res.push([...arr]); // 将当前符合的组合推入结果中
      return;
    }
    for (let i = start; i <= n; i++) {
      // 遍历所有选择
      arr.push(i); // 当前选择
      helper(i + 1, arr); // 继续选择
      arr.pop(); // 撤销当前选择
    }
  };

  helper(1, []);

  return res;
};

组合总和

题目地址 (opens new window)

var combinationSum = function(candidates, target) {
  const res = [];

  const helper = (start, arr, sum) => {
    if (sum >= target) {
      if (sum === target) {
        res.push(arr.slice());
      }
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      arr.push(candidates[i]);
      helper(i, arr, sum + candidates[i]);
      arr.pop();
    }
  };

  helper(0, [], 0);

  return res;
};

组合总和 II

题目地址 (opens new window)

var combinationSum2 = function(candidates, target) {
  const res = [];
  candidates.sort();

  const helper = (start, arr, sum) => {
    if (sum >= target) {
      if (sum === target) {
        res.push(arr.slice());
      }
      return;
    }
    for (let i = start; i < candidates.length; i++) {
      if (i > start && candidates[i - 1] === candidates[i]) {
        continue;
      }
      arr.push(candidates[i]);
      helper(i + 1, arr, sum + candidates[i]);
      arr.pop();
    }
  };

  helper(0, [], 0);

  return res;
};

组合总和 III

题目地址 (opens new window)

var combinationSum3 = function(k, n) {
  const res = [];

  const helper = (start, arr, sum) => {
    if (arr.length === k) {
      if (sum === n) {
        res.push(arr.slice());
      }
      return;
    }
    for (let i = start; i <= 9; i++) {
      arr.push(i);
      helper(i + 1, arr, sum + i);
      arr.pop();
    }
  };

  helper(1, [], 0);

  return res;
};

全排列 ✅

题目地址 (opens new window)

// 回溯法：每一层枚举 “下一个可以放的数”，放完 n 个数就得到一个排列
// 时间复杂度 O(n × n!)：一共有 n! 个排列，每个排列在 arr.slice() 拷贝时花费 O(n)
// 空间复杂度 O(n)：不算 res 存储结果的开销，递归栈深度 + arr 长度都是 O(n)
var permute = function(nums) {
  const res = []; // 收集所有排列结果

  // arr：当前正在构造的排列（路径）
  const helper = (arr) => {
    if (arr.length === nums.length) {
      // 路径长度等于 nums 长度，说明已经选完所有数，记录这一个排列
      res.push(arr.slice()); // 用 slice 拷贝，避免后续回溯修改到 res 里保存的结果
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      // arr.includes 用来判断 nums[i] 是否已经被选过，未选过才能继续选
      if (!arr.includes(nums[i])) {
        arr.push(nums[i]); // 做选择：把 nums[i] 加入当前路径
        helper(arr); // 基于新路径继续往下选
        arr.pop(); // 撤销选择（回溯），尝试路径的下一种可能

        // 另一种写法：用 concat 生成新数组传入，不修改原 arr，天然不需要 pop 撤销
        // 但 concat 每次都拷贝数组，时间和空间开销比 push/pop 版本更高
        // helper(arr.concat(nums[i]));
      }
    }
  };

  helper([]); // 从空路径开始构造

  return res;
};

全排列 II

题目地址 (opens new window)

var permuteUnique = function(nums) {
  const res = [];
  const visited = [];
  nums.sort();

  const helper = (arr) => {
    if (arr.length === nums.length) {
      res.push(arr.slice());
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (visited[i] || (i > 0 && nums[i - 1] === nums[i] && !visited[i - 1])) {
        continue;
      }
      arr.push(nums[i]);
      visited[i] = 1;
      helper(arr);
      arr.pop();
      visited[i] = 0;
    }
  };

  helper([]);

  return res;
};

N 皇后

题目地址 (opens new window)

const solveNQueens = (n) => {
  const board = new Array(n);
  for (let i = 0; i < n; i++) {
    board[i] = new Array(n).fill("."); // 创建棋盘
  }

  const cols = new Set(); // 列
  const leftDiag = new Set(); // 左对角线
  const rightDiag = new Set(); // 右对角线
  const res = [];

  const helper = (row) => {
    if (row === n) {
      const stringsBoard = board.slice();
      for (let i = 0; i < n; i++) {
        stringsBoard[i] = stringsBoard[i].join("");
      }
      res.push(stringsBoard);
      return;
    }
    for (let col = 0; col < n; col++) {
      // 如果当前点的所在的列和左右对角线任意一处有皇后，那么跳过该点
      if (cols.has(col) || leftDiag.has(row + col) || rightDiag.has(row - col))
        continue;
      // 放置皇后，并将对应的列和左右对角线记录下来
      board[row][col] = "Q";
      cols.add(col);
      rightDiag.add(row - col);
      leftDiag.add(row + col);

      // 递归下一行
      helper(row + 1);

      // 恢复现场，撤销该点的皇后，并删掉对应的列和左右对角线记录
      board[row][col] = ".";
      cols.delete(col);
      rightDiag.delete(row - col);
      leftDiag.delete(row + col);
    }
  };
  helper(0);
  return res;
};

N 皇后 II

题目地址 (opens new window)

const totalNQueens = (n) => {
  const cols = new Set();
  const leftDiag = new Set();
  const rightDiag = new Set();
  let count = 0;

  const helper = (row) => {
    if (row >= n) return count++;

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || leftDiag.has(row + col) || rightDiag.has(row - col))
        continue;

      cols.add(col);
      leftDiag.add(row + col);
      rightDiag.add(row - col);

      helper(row + 1);

      cols.delete(col);
      leftDiag.delete(row + col);
      rightDiag.delete(row - col);
    }
  };
  helper(0);

  return count;
};

cosnt totalNQueens = (n) => {
  let count = 0;

  const dfs = (row, col, leftDiag, rightDiag) => {
    if (row >= n) {
      count++;
      return;
    }

    // 得到当前层所有的空位，即可以放置皇后的位置；同时将这些空位转成 1，已经放置了皇后的位置转成 0
    let bits = (~(col | leftDiag | rightDiag)) & ((1 << n) - 1);

    while (bits) {
      const one = bits & -bits; // 得到最低位的 1
      dfs(row + 1, col | one, (leftDiag | one) << 1, (rightDiag | one) >> 1); // 更新行、列和左右对角线，进行新一轮的遍历
      bits = bits & (bits - 1); // 去掉最低位的 1
    }
  };

  dfs(0, 0, 0, 0);
  return count;
};

单词搜索

题目地址 (opens new window)

var exist = function(board, word) {
  const row = board.length;
  const col = board[0].length;
  const visited = new Array(row); // 与 board 一样大的二维数组，用于标记当前点是否访问过
  for (let i = 0; i < row; i++) {
    visited[i] = new Array(col);
  }

  const dfs = function(r, c, i) {
    // r 是当前点的横坐标，c 是当前点的纵坐标，i 是当前检查的单词中的字符索引
    if (i === word.length) {
      // 递归出口，遍历完当前检查的单词
      return true;
    }
    if (r < 0 || r >= row || c < 0 || c >= col) {
      // 当前点坐标越界
      return false;
    }
    if (visited[r][c] || board[r][c] !== word[i]) {
      // 当前点已经访问过或者它不是目标点
      return false;
    }
    visited[r][c] = true; // 标记当前点已被访问过
    const next =
      dfs(r - 1, c, i + 1) ||
      dfs(r + 1, c, i + 1) ||
      dfs(r, c - 1, i + 1) ||
      dfs(r, c + 1, i + 1); // 检查当前点的上下左右四个点能否找到下一个字符
    if (next) {
      return true;
    }
    visited[r][c] = false; // 如果不能找到下一个字符，需要撤销当前点的访问状态
    return false;
  };

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (board[i][j] === word[0] && dfs(i, j, 0)) {
        // 找到递归起点，并且递归结果为真
        return true;
      }
    }
  }

  return false;
};

单词搜索 II

题目地址 (opens new window)

// 回溯 + 字典树
const findWords = (board, words) => {
  const row = board.length;
  const col = board[0].length;
  const res = [];

  // 构建字典树
  const getTrie = (words) => {
    let root = Object.create(null);
    for (const word of words) {
      let node = root;
      for (let c of word) {
        if (!node[c]) {
          node[c] = Object.create(null);
        }
        node = node[c];
      }
      node.word = word;
    }
    return root;
  };

  const dfs = (r, c, trie) => {
    if (trie.word) {
      res.push(trie.word);
      trie.word = null;
    }

    // 边界条件
    if (r < 0 || r >= row || c < 0 || c >= col) return;

    // 当前字符不在字典树中
    if (!trie[board[r][c]]) return;

    const temp = board[r][c];
    board[r][c] = "#"; // 标记当前点已经访问过
    dfs(r - 1, c, trie[temp]);
    dfs(r + 1, c, trie[temp]);
    dfs(r, c - 1, trie[temp]);
    dfs(r, c + 1, trie[temp]);
    board[r][c] = temp; // 遍历完当前点的上下左右 4 个点之后恢复现场
  };

  const trie = getTrie(words);
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      dfs(i, j, trie);
    }
  }

  return res;
};

电话号码的字母组合

题目地址 (opens new window)

// DFS
var letterCombinations = function(digits) {
  if (!digits.length) return [];
  const res = [];
  const map = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz"
  };

  const dfs = (cur, i) => {
    // cur 是当前构建的字符串，i 是扫描的指针
    if (i > digits.length - 1) {
      // 指针越界，递归的出口
      res.push(cur); // 将解推入结果中
      return; // 结束当前递归分支，进入另一个递归分支
    }
    const letters = map[digits[i]]; // 当前数字对应哪些字母
    for (const c of letters) {
      // 不同的字母选择代表不同的递归分支
      dfs(cur + c, i + 1); //递归
    }
  };

  dfs("", 0);

  return res;
};

// BFS
var letterCombinations = function(digits) {
  if (!digits.length) return [];
  const queue = [];
  const map = {
    "2": "abc",
    "3": "def",
    "4": "ghi",
    "5": "jkl",
    "6": "mno",
    "7": "pqrs",
    "8": "tuv",
    "9": "wxyz"
  };
  queue.push("");

  for (let i = 0; i < digits.length; i++) {
    // bfs 的层数，即 digits 的长度
    const count = queue.length; // 当前层的节点个数
    for (let j = 0; j < count; j++) {
      const cur = queue.shift(); // 让当前层的节点逐个出队
      const letters = map[digits[i]];
      for (const c of letters) {
        queue.push(cur + c); // 生成新的字母串入列
      }
    }
  }

  return queue; // 队列中全是最后一层生成的字母串
};