组合去重的核心哲学：有序唯一性 (Ordered Uniqueness)

在上一篇文章《含有重复元素的全排列去重》中，我们详细拆解了如何用 DFS 的剪枝逻辑来消灭重复的排列分支。

但如果我们跳出代码本身，从更高的思维维度来看组合数学里的“去重”问题，你会发现不管是组合（Combinations）还是去重排列（Unique Permutations），它们背后共享着一个极其优美而深刻的核心哲学。

你用四个字精准地概括了它：有序唯一性。

什么是“有序唯一性”？

假设我们要从 [1, 2, 3] 里面选 2 个数字（不关心顺序，即求组合）。 如果我们用最暴力的双重循环去选，会选出 (1, 2)，也会选出 (2, 1)。在组合的概念里，它们是重复的。

如何消灭这种重复？ 最笨的办法是：全都生成出来，放进一个 Set 里去重。 最高级的办法是（也是算法的本质思路）：建立一套严苛的“出场顺序规则”。

我们强行规定：选出来的序列，必须是严格递增的。

• (1, 2) 是递增的，合法，留下。
• (2, 1) 是递减的，非法，直接从源头掐断。

一旦引入了“有序”这个强硬的规则，无序的组合状态就被坍缩成了唯一的一种合法表达形式。这就是“有序唯一性”。

“有序唯一性”在各大算法中的体现

一旦你戴上“有序唯一性”这副眼镜，很多原本死记硬背的模板代码就全都豁然开朗了。

1. 为什么手写组合 DFS 时，要传一个 start_index？

如果你在 C++ 或 Python 里手写过 $C(N, K)$ 的回溯代码，你一定对 start_index 这个变量不陌生。

 1ans = []
 2path = []
 3
 4# start_idx 就是维持“有序唯一性”的灵魂
 5def dfs_combination(start_idx, k, n):
 6    if len(path) == k:
 7        ans.append(path[:])
 8        return
 9        
10    for i in range(start_idx, n + 1):
11        path.append(i)
12        # 递归下一层时，起点必须是 i + 1
13        dfs_combination(i + 1, k, n)
14        path.pop()
15
16dfs_combination(1, 2, 3)

解析： 为什么下一层的循环起点是 i + 1？ 这就是在强制执行有序性！因为我已经选了 2，那么之后选的数字必须在我的后面（必须大于我）。这就从根本上杜绝了选出 (2, 1) 这种递减序列的可能。

2. 为什么 itertools.combinations_with_replacement 是非降序的？

我们在之前讨论《有放回的组合》时提到，combinations_with_replacement([1, 2, 3, 4], 3) 生成的结果总是像 (1, 2, 2), (1, 3, 4) 这样按从小到大排好序的。

其实它的底层实现同样应用了“有序唯一性”：既然允许重复选，那么我制定的规则就从“严格递增（大于我）”稍微放宽一点，变成了**“非严格递增（大于等于我）”**。 这样，既保证了可以选 (2, 2)，又永远不会生成非法的 (2, 1)。

3. 重温 unique_permutations 的剪枝

现在我们带着“有序唯一性”的视角，再来看上一篇的全排列去重：

1if i > 0 and items[i] == items[i - 1] and not used[i - 1]:
2    continue

假设我们有 [1A, 1B, 1C]。它们是相同的数字，本质上它们内部是一个无序的组合。 如果我们放任不管，它们之间会产生 (1A, 1B, 1C), (1B, 1C, 1A) 等 $3! = 6$ 种乱七八糟的排列。

这行代码在干嘛？ 它在给这几个相同长相的克隆人强行赋予一个“出场顺序”： “你们必须按照 A -> B -> C 的顺序出场！”

既然规定了必须按字典序（或说相对顺序）出场，那么在这 6 种混战中，唯一合法的就是 (1A, 1B, 1C)。 通过维护相同元素的内部有序唯一性，我们完美消灭了外部表现出的重复。

总结：从术到道

当你初学暴力算法时，你记住的是：

• 手写组合要传 start_index
• 数组去重要先 sort 再判断 items[i] == items[i-1]

但现在你领悟了： 这一切防重复的操作，本质都是在混乱无序的状态空间里，寻找一种可以人为强加的“单调序列”（严格单调或非严格单调）。

有序即唯一，单调即去重。 这就是组合数学与深度优先搜索算法交汇处，最优雅的设计哲学。