分治回溯

分治

分治是一种非常重要且常见的算法策略。分治通常基于递归实现，包括“分”和“治”两个步骤。

• 分（划分阶段）：递归地将原问题分解为两个或多个子问题，直至到达最小子问题时终止。
• 治（合并阶段）：从已知解的最小子问题开始，从底至顶地将子问题的解进行合并，从而构建出原问题的解。

如何判断

“归并排序”是分治策略的典型应用之一。是否适合用分治解决问题，通常可参考以下几个依据。

• 问题可以分解：原问题可分解成规模更小、类似的子问题，并能够以相同方式递归地进行划分。
• 子问题是独立的：子问题之间没有重叠，互不依赖，可以独立解决。
• 子问题的解可以合并：原问题的解通过合并子问题的解得来。

显然，归并排序满足以上三个判断依据。

• 问题可以分解：递归地将数组（原问题）划分为两个子数组（子问题）。
• 子问题是独立的：每个子数组都可以独立地进行排序（子问题可以独立进行求解）。
• 子问题的解可以合并：两个有序子数组（子问题的解）可以合并为一个有序数组（原问题的解）。

提高效率

• 操作数量优化
• 并行计算优化

常见应用

一方面，分治可以用来解决许多经典算法问题。

• 寻找最近点对：该算法首先将点集分成两部分，然后分别找出两部分的最近点对，最后找出跨越两部分的最近点对。
• 大整数乘法：例如 Karatsuba 算法，它将大整数乘法分解为几个较小的整数的乘法和加法。
• 矩阵乘法：例如 Strassen 算法，它将大矩阵乘法分解为多个小矩阵的乘法和加法。
• 汉诺塔问题：汉诺塔问题可以通过递归解决，这是典型的分治策略应用。
• 求解逆序对：在一个序列中，如果前面的数字大于后面的数字，那么这两数字构成一个逆序对。求解逆序对问题可以利用分治的思想，借助归并排序进行求解。

另一方面，分治在算法和数据结构的设计中应用得非常广泛。

• 二分查找：二分查找是将有序数组从中点索引处分为两部分，然后根据目标值与中间元素值比较结果，决定排除哪一半区间，并在剩余区间执行相同的二分操作。
• 归并排序
• 快速排序：快速排序是选取一个基准值，然后把数组分为两个子数组，其中一个子数组的元素比基准值小，另一子数组的元素比基准值大，再对这两部分进行相同的划分操作，直至子数组只剩下一个元素。
• 桶排序：桶排序的基本思想是将数据分散到多个桶，然后再对每个桶内的元素进行排序，最后将各个桶的元素依次取出，从而得到一个有序数组。
• 树：例如二叉搜索树、AVL 树、红黑树、B 树、B+ 树等，它们的查找、插入和删除等操作都可以视为分治策略的应用。
• 堆：堆是一种特殊的完全二叉树，其各种操作，如插入、删除和堆化，实际都隐含分治的思想。
• 哈希表：虽然哈希表并不直接应用分治，但某些哈希冲突解决方案间接应用了分治策略，例如，链式地址中的长链表会被转化为红黑树，以提升查询效率。

分治是一种“润物细无声”的算法思想，隐含在各种算法与数据结构之中。

回溯

回溯算法是一种通过穷举来解决问题的方法，核心思想是从一个初始状态出发，暴力搜索所有可能的解决方案，当遇到正确的解则将其记录，直到找到解或者尝试了所有可能的选择都无法找到解为止。回溯算法通常采用“深度优先搜索”来遍历解空间。

给定一棵二叉树，搜索并记录所有值为 7 的节点，请返回节点列表。

/* 前序遍历：例题一 */
function preOrder(root, res) {
  if (root === null) {
    return;
  }
  if (root.val === 7) {
    // 记录解
    res.push(root);
  }
  preOrder(root.left, res);
  preOrder(root.right, res);
}

尝试与回退

之所以称之为回溯算法，是因为该算法在搜索解空间时会采用“尝试”与“回退”的策略。当算法在搜索过程中遇到某个状态无法继续前进或无法得到满足条件的解时，它会撤销上一步的选择，退回到之前状态，并尝试其他可能的选择。对于例题一，访问每个节点都代表一次“尝试”，而越过叶节点或返回父节点的 return 则表示“回退”。但回退并不仅仅包括函数返回。如：

在二叉树中搜索所有值为 7 的节点，请返回根节点到这些节点的路径。

/* 前序遍历：例题二 */
function preOrder(root, path, res) {
  if (root === null) {
    return;
  }
  path.push(root);
  if (root.val === 7) {
    // 记录解
    res.push([...path]);
  }
  preOrder(root.left, res);
  preOrder(root.right, res);
  path.pop();
}

在每次“尝试”中，我们通过将当前节点添加进 path 来记录路径；而在“回退”前，我们需要将该节点从 path 中弹出，以恢复本次尝试之前的状态。可将尝试和回退理解为“前进”与“撤销”，两个操作互逆。

剪枝

复杂的回溯问题通常包含一个或多个约束条件，约束条件通常可用于“剪枝”。

在二叉树中搜索所有值为 7 节点，请返回根节点到这些节点的路径并要求路径中不包含值为 3 节点。

/* 前序遍历：例题三 */
function preOrder(root, path, res) {
  // 剪枝
  if (root === null || root.val === 3) {
    return;
  }
  // 尝试
  path.push(root);
  if (root.val === 7) {
    // 记录解
    res.push([...path]);
  }
  preOrder(root.left, path, res);
  preOrder(root.right, path, res);
  // 回退
  path.pop();
}

框架

将回溯的“尝试、回退、剪枝”的主体框架提炼出来，提升代码的通用行：

/* 回溯算法框架 */
function backtrack(state, choices, res) {
  // 判断是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
    // 不再继续搜索
    return;
  }
  // 遍历所有选择
  for (let choice of choices) {
    // 剪枝：判断选择是否合法
    if (isValid(state, choice)) {
      // 尝试：做出选择，更新状态
      makeChoice(state, choice);
      backtrack(state, choices, res);
      // 回退：撤销选择，恢复到之前的状态
      undoChoice(state, choice);
    }
  }
}

/* 判断当前状态是否为解 */
function isSolution(state) {
  return state && state[state.length - 1]?.val === 7;
}

/* 记录解 */
function recordSolution(state, res) {
  res.push([...state]);
}

/* 判断在当前状态下，该选择是否合法 */
function isValid(state, choice) {
  return choice !== null && choice.val !== 3;
}

/* 更新状态 */
function makeChoice(state, choice) {
  state.push(choice);
}

/* 恢复状态 */
function undoChoice(state) {
  state.pop();
}

/* 回溯算法：例题三 */
function backtrack(state, choices, res) {
  // 检查是否为解
  if (isSolution(state)) {
    // 记录解
    recordSolution(state, res);
  }
  // 遍历所有选择
  for (const choice of choices) {
    // 剪枝：检查选择是否合法
    if (isValid(state, choice)) {
      // 尝试：做出选择，更新状态
      makeChoice(state, choice);
      // 进行下一轮选择
      backtrack(state, [choice.left, choice.right], res);
      // 回退：撤销选择，恢复到之前的状态
      undoChoice(state);
    }
  }
}

基于回溯算法框架的代码实现虽然显得啰唆，但通用性更好。实际上，许多回溯问题可以在该框架下解决。只需根据具体问题来定义 state 和 choices ，并实现框架中的各个方法即可。

优缺点

回溯算法本质上是一种深度优先搜索算法，它尝试所有可能的解决方案直到找到满足条件的解。这种方法的优点在于能够找到所有可能的解决方案，而且在合理的剪枝操作下，具有很高的效率。然而，在处理大规模或者复杂问题时，回溯算法的运行效率可能难以接受。

• 时间：回溯算法通常需要遍历状态空间的所有可能，时间复杂度可以达到指数阶或阶乘阶
• 空间：在递归调用中需要保存当前的状态（例如路径、用于剪枝的辅助变量等），当深度很大时，空间需求可能会变得很大

即便如此，回溯算法仍然是某些搜索问题和约束满足问题的最佳解决方案。对于这些问题，由于无法预测哪些选择可生成有效的解，因此我们必须对所有可能的选择进行遍历。在这种情况下关键是如何优化效率，常见的效率优化方法有两种。

• 剪枝：避免搜索那些肯定不会产生解的路径，从而节省时间和空间
• 启发式搜索：在搜索过程中引入一些策略或者估计值，从而优先搜索最有可能产生有效解的路径

典型例题

回溯算法可用于解决许多搜索问题、约束满足问题和组合优化问题。

搜索问题：这类问题的目标是找到满足特定条件的解决方案。

• 全排列问题：给定一个集合，求出其所有可能的排列组合。
• 子集和问题：给定一个集合和一个目标和，找到集合中所有和为目标和的子集。
• 汉诺塔问题：给定三根柱子和一系列大小不同的圆盘，要求将所有圆盘从一根柱子移动到另一根柱子，每次只能移动一个圆盘，且不能将大圆盘放在小圆盘上。

约束满足问题：这类问题的目标是找到满足所有约束条件的解。

• n 皇后：在 n*n 的棋盘上放置 n 个皇后，使得它们互不攻击。
• 数独：在 99 的网格中填入数字 1~9，使得每行、每列和每个 33 子网格中的数字不重复。
• 图着色问题：给定一个无向图，用最少的颜色给图的每个顶点着色，使得相邻顶点颜色不同。

组合优化问题：这类问题的目标是在一个组合空间中找到满足某些条件的最优解。

• 0-1 背包问题：给定一组物品和一个背包，每个物品有一定价值和重量，要求在背包容量限制内选择物品使得总价值最大。
• 旅行商问题：在一个图中，从一个点出发，访问所有其他点恰好一次后返回起点，求最短路径。
• 最大团问题：给定一个无向图，找到最大的完全子图，即子图中任意两顶点之间都有边相连。

请注意，对于许多组合优化问题，回溯不是最优解决方案。

• 0-1 背包问题通常使用动态规划解决，以达到更高的时间效率。
• 旅行商是一个著名的 NP-Hard 问题，常用解法有遗传算法和蚁群算法等。
• 最大团问题是图论中的一个经典问题，可用贪心算法等启发式算法来解决。