算法06：分治、回溯与贪心的选择依据

递归是代码的组织方式，分治、回溯与贪心是解决问题的策略。分治把一个问题拆成较小的问题并合并答案；回溯保留多种选择，沿搜索树生成候选；贪心在有证明的条件下只保留一个局部选择。它们需要不同的正确性理由，不能把“用了递归”当成算法设计已经完成。

1. 递归先说清三件事

一个递归函数需要明确状态、终止条件和进展。例如排序 [lo,hi)：

“区间长度严格变短”保证不会无限递归。调用栈也是存储，不能因为没有显式 new 就写额外空间 O(1)。深度为 n 的递归在大输入上可能耗尽栈；适合的小输入枚举与适合的大数据实现应分开考虑。

2. 分治：归并时一起统计逆序对

逆序对定义为下标 i<j 但值 a[i]>a[j]。序列 [3,1,2,1] 有 4 对：第一个 3 与后面三个数，以及 2 与末尾的 1。相等值不属于逆序对。

直接双重循环为 O(n²)。分治按下标中点拆开后，逆序对只有三种：左半内部、右半内部、跨越左右两半。前两种由递归解决，最后一种在归并时统计。

当左右两半已有序，若 left[i] > right[j]，左半从 i 起的所有剩余值都大于 right[j]，可以一次增加 mid-i 对，而无需逐项比较：

while (i < mid && j < hi) {
    if (a[i] <= a[j]) temp[out++] = a[i++];
    else {
        temp[out++] = a[j++];
        count += static_cast<long long>(mid - i);
    }
}

这里使用 <= 很重要：值相等时先取左侧，不计逆序，同时保留相等记录原有顺序。这与“排序稳定性”联系起来，而不仅是一个可随意改写的比较符号。

[3,1,2,1] 的合并过程

顶层先取左侧 1；右侧 1 小于左侧剩余的 3，增加 1；随后右侧 2 也小于 3，再增加 1。每个跨区间逆序对恰好在其左右元素首次分属两个子区间的那层被计入，不会重复计数。

每层合并总计 O(n)，递归深度 O(log n)，时间 O(n log n)。复用长度 n 的缓冲区，额外空间 O(n)，调用栈 O(log n)。逆序序列的最大计数 n(n−1)/2，n=100000 时为 4999950000，已经超出有符号 32 位整数。

分治不只用于排序：几何最近点对、快速幂、树上汇总也会拆问题。不过拆开之后怎样合并、子问题是否真能独立解决，需要根据目标单独说明。

3. 回溯：选择、递归、撤销

生成全排列需要保留分支。以 [1,2,3] 为例，第一位可以选任一未使用元素，第二位从剩余元素中选择，第三位再填最后一个。

used[i] = true;
path.push_back(a[i]);
permute(a, used, path, result);
path.pop_back();
used[i] = false;

每次递归入口的不变量是：path 恰好包含已选前缀，used 恰好标记这些位置。返回时必须恢复进入分支之前的状态，否则同层的下一条分支会继承上一条的选择。输出也必须保存 path 的一份副本，不能让全部答案引用同一个不断变化的路径。

[]
├─ [1] ─ [1,2] ─ [1,2,3]
│       └ [1,3] ─ [1,3,2]
├─ [2] ─ [2,1] ─ [2,1,3]
│       └ [2,3] ─ [2,3,1]
└─ [3] ─ [3,1] ─ [3,1,2]
        └ [3,2] ─ [3,2,1]

如果 n 个值全不同，输出本来就有 n! 个排列，每个排列长度 n，仅写出答案就需要 Ω(n·n!)。配套的逐位置扫描实现整体为 O(n·n!)，路径与标记空间 O(n)，存储全部结果还需要 O(n·n!)。不能把“剪枝”当成自动摆脱输出规模的办法。

4. 重复元素：同层只保留一个等价选择

对 [1,1,2]，按位置区分两个 1 会生成重复答案。先排序，再加入：

if (used[i]) continue;
if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;

第二条限制的含义是：在同一层，前面的相同值尚未选择时，不再从后面的相同值开一个等价分支。若前一个 1 已在当前路径中，第二个 1 仍能在下一层使用。 不能直接写成“相等就跳过”，否则会连合法的 [1,1,2] 一起删掉。

得到的不同排列是 [1,1,2]、[1,2,1]、[2,1,1]。空输入也有一个合法排列：空排列。这与“没有找到答案”应返回空列表不同。

剪枝必须证明剩余分支不会成功

组合求和中，若剩余值都非负且当前和已经大于目标，则继续加入元素不会把和降回目标，可以剪枝。如果有负值，当前 8、目标 5、后面还有 −3，这条剪枝就会错删答案。

另一个合法剪枝是用剩余元素提供上下界：即使把可用正值都加上也达不到目标，可以停止；但上下界必须包含所有可能完成方式，不能拿一个“看起来典型”的完成方式充当界限。

回溯适合生成方案、约束满足、小规模搜索。若大量分支进入相同的未来状态，可以用记忆化搜索消除重复；若状态定义和依赖顺序清楚，还可以写成动态规划。缓存键要包含真正影响未来的全部信息，而不仅是递归深度。

5. 贪心：区间调度为什么选最早结束

给定正长度的半开时间区间 [start,finish)，希望选出最多个互不重叠的区间。相邻区间可以首尾相接，因为结束时刻不属于前一个区间。

正确策略是按结束时刻升序排列，每次选择与已选部分兼容的第一个区间：

for (const auto& interval : sorted_by_finish) {
    if (selected.empty() || interval.start >= selected.back().finish)
        selected.push_back(interval);
}

对 [0,3)、[2,4)、[3,5)、[5,7)、[0,8)，选择 [0,3)、[3,5)、[5,7)，共 3 个。排序 O(n log n)，扫描 O(n)；若只返回数量，扫描额外空间 O(1)，保存方案则需要 O(n)。

交换论证

设 E 是所有候选中结束最早的区间，某个最优方案第一个区间为 O。由于 finish(E) <= finish(O)，用 E 替换 O 后，后面的区间仍与它兼容，方案数量不减少。因此至少存在一个以 E 开始的最优方案。对 E 之后的剩余问题重复同样论证，得到整个贪心方案最优。

这份证明解释了为何可以永久丢弃其他当前选择，而不回头枚举。排序规则来自问题目标，不来自“贪心一般都快”的经验。

6. 两种直觉策略为什么会失败

若区间带有收益，目标变成最大总收益，最早结束也不再适用：[0,2) 收益 1 与 [0,3) 收益 100，贪心会错选前者。加权区间调度需要综合“选当前区间”和“不选当前区间”的收益，通常使用动态规划。

同样，硬币最少数中的“每次选最大面值”并非对任意硬币系统都正确。遇到一个局部策略，先明确需要证明哪条交换或支配关系，再决定是否能称为贪心算法。

7. 三种策略怎样比较

search_greedy.cpp 提供归并逆序对、去重全排列、区间调度。1800 组固定随机种子的案例分别与双重循环、标准库排列枚举、所有区间子集枚举对照；另有 100000 个逆序值验证计数范围。

继续看动态规划的状态与方案恢复，或返回专题路线。