跳到主要内容

回溯✅

打印所有长度为 n 的二进制数​

/**
 * 打印所有长度为 n 的二进制数
 * 输入：n = 2
 * 输出：['00', '01', '10', '11']
 */
function printBinary (n) {

}
答案
function printBinary (n) {
  if (n === 0) return []

  const result = []
  function backtrack (path = []) {
    if (path.length === n) {
      result.push(path.join(''))
      return
    }
    backtrack([...path, '0'])
    backtrack([...path, '1'])
  }
  backtrack()
  return result
}

module.exports = printBinary

Open browser consoleTests

子集​

/**
 * 子集
 * 输入：[1,2,3]
 * 输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
 */
function subsets (nums) {

}
答案
function subsets (nums) {
  if (nums.length === 0) return [[]]

  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) // 递归到下一个元素
      path.pop() // 撤销选择
    }
  }
  backtrack(0, [])
  return result
}
module.exports = subsets

Open browser consoleTests

组合问题​

/**
 * 组合问题
 * 输入：n = 4, k = 2
 * 输出：[[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
 */
function combine (n, k) {

}
答案
function combine (n, k) {
  if (n === 0) return []
  const result = []
  function backtrack (start, path) {
    if (path.length === k) {
      result.push([...path]) // 组合数量达到 k，加入结果
      return
    }
    for (let i = start; i <= n; i++) {
      path.push(i)
      backtrack(i + 1, path)
      path.pop() // 撤销选择
    }
  }
  backtrack(1, [])
  return result
}
module.exports = combine

Open browser consoleTests

全排列​

/**
 * 全排列
 * 输入：[1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
function permute (nums) {

}
答案
/**
 * 生成数组中所有可能的排列组合。
 *
 * 递推公式：
 * 设P(S)表示集合S的所有排列
 * 对于数组[n₁, n₂, ..., nₘ]：
 * P({n₁, n₂, ..., nₘ}) = ⋃ {nᵢ} × P({n₁, ..., nᵢ₋₁, nᵢ₊₁, ..., nₘ})
 *
 * 其中i从1到m，"×"表示将元素nᵢ添加到剩余元素所有排列的前面。
 * 基本情况：当S为空集时，P(S) = {[]}（仅包含空排列）
 */
function permute (nums) {
  // 处理边界情况：空数组
  if (nums.length === 0) return []

  const result = [] // 存储所有找到的排列结果

  /**
    * 回溯函数，用于生成所有可能的排列
    * @param {number[]} path - 当前正在构建的排列路径
    * @param {number[]} choices - 当前可以选择的剩余数字
    */
  const backtrack = (path, choices) => {
    // 基本情况：如果路径长度等于原始数组长度，则找到一个完整的排列
    if (path.length === nums.length) {
      result.push(path.slice()) // 将当前排列的副本添加到结果中
      return
    }

    // 遍历所有可用的选择
    for (let i = 0; i < choices.length; i++) {
      // 做出选择：将当前数字添加到路径中
      path.push(choices[i])

      // 创建新的选择集（排除已选择的元素）
      const newChoices = choices.slice()
      newChoices.splice(i, 1)

      // 递归：使用更新后的路径和选择继续探索
      backtrack(path, newChoices)

      // 回溯：撤销选择，从路径中移除最后添加的元素
      path.pop()
    }
  }

  // 开始回溯过程，初始路径为空，所有数字都可选择
  backtrack([], nums)
  return result
}

module.exports = permute

Open browser consoleTests

组合总和​

/**
 * 组合总和
 * 输入：candidates = [2,3,6,7], target = 7
 * 输出：[[2,2,3],[7]]
 */
function combinationSum (candidates, target) {

}
答案
function combinationSum (candidates, target) {
  if (!candidates || !candidates.length) return []
  const result = []
  function backtrack (start, path, sum) {
    if (sum === target) {
      result.push([...path]) // 找到一个符合条件的组合
      return
    }
    if (sum > target) return // 剪枝
    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i])
      backtrack(i, path, sum + candidates[i]) // 允许重复选择
      path.pop() // 撤销选择
    }
  }
  backtrack(0, [], 0)
  return result
}
module.exports = combinationSum

Open browser consoleTests

N 皇后问题​

/**
 * N 皇后问题
 * 输入：n = 4
 * 输出：[['.Q..','...Q','Q...','..Q.'],['..Q.','Q...','...Q','.Q..']]
 */
function solveNQueens (n) {

}
答案
function solveNQueens (n) {
  if (n === 0) return []
  const result = []
  const board = Array.from({ length: n }, () => '.'.repeat(n))
  const columns = new Set()
  const diagonals1 = new Set()
  const diagonals2 = new Set()

  function backtrack (row) {
    if (row === n) {
      result.push([...board]) // 找到一个解
      return
    }
    for (let col = 0; col < n; col++) {
      if (columns.has(col) || diagonals1.has(row - col) || diagonals2.has(row + col)) continue
      board[row] = board[row].substring(0, col) + 'Q' + board[row].substring(col + 1)
      columns.add(col)
      diagonals1.add(row - col)
      diagonals2.add(row + col)
      backtrack(row + 1)
      board[row] = '.'.repeat(n)
      columns.delete(col)
      diagonals1.delete(row - col)
      diagonals2.delete(row + col)
    }
  }

  backtrack(0)
  return result
}

module.exports = solveNQueens

Open browser consoleTests

回溯​

题目是给一串数字（0-9）每个数字之间可以加+-号或者不加，组成的表达式Q计算结果等于 给定的目标数，输出所有满足条件的表达式。
例如：［123456789］ 目标 100 可能的组合：

1+23-4+56+7+8+9
-1-2+34-5-6+78+9
22%