算法-排列组合大乱炖

medium / hard 里总有一批题目涉及"排列""组合""子集""幂集""笛卡尔积"，看着各不相同，其实就那么几个递归模板。这篇把常见的 5 种算法统一讲清楚。

笛卡尔积

最基础也是最常被复用的操作。给两个集合 A 和 B，生成所有 (a, b) 组合。

// 两个联合的笛卡尔积：返回字符串形式的联合
type Cartesian<A extends string, B extends string> = `${A}-${B}`;

type R = Cartesian<'x' | 'y', '1' | '2'>;
// 'x-1' | 'x-2' | 'y-1' | 'y-2'

原理：模板字符串 ${A}${B} 在 A/B 是联合时会分发，自动生成所有组合。这是 TS 里做笛卡尔积最省力的手段。

对非字符串场景（比如要得到元组对），就要显式分发：

type CartesianTuple<A, B> = A extends any
  ? B extends any
    ? [A, B]
    : never
  : never;

type R2 = CartesianTuple<'a' | 'b', 1 | 2>;
// ['a', 1] | ['a', 2] | ['b', 1] | ['b', 2]

组合（C(n, 2)）

"从一个集合里任意选两个，可无序不重复"。

type Combination<T extends string> = T extends any
  ? Exclude<T, T> extends never
    ? never
    : `${T}${'' | ` ${Combination<Exclude<T, T>>}`}`
  : never;

更常见的思路是先拆一项，再对剩下递归：

type Combo<T extends string, Prev extends string = ''> = T extends any
  ? Prev extends ''
    ? T | Combo<Exclude<T, T>, T> extends never
      ? T
      : never
    : `${Prev} ${T}` | Combo<Exclude<T, T>, `${Prev} ${T}`>
  : never;

题目 medium/8767-Combination 用的是 union 变换配合 UnionToIntersection 的巧妙写法。简单说"组合"的核心：

1. 对联合每一支分发；
2. 分发的当前支选或不选；
3. 剩余部分递归继续。

全排列

"把 n 个元素排成一列，按顺序，有 n! 种"。

type Permutation<T, Copy = T> = [T] extends [never]
  ? []
  : T extends any
  ? [T, ...Permutation<Exclude<Copy, T>>]
  : never;

type R = Permutation<'a' | 'b' | 'c'>;
// ['a','b','c'] | ['a','c','b'] | ['b','a','c'] | ...

解读：

• 第一次分发选一个作为首元素；
• 从剩余集合 Exclude<Copy, T> 里递归排列；
• 递归出口：联合为空返回 []。

注意 [T] extends [never] 的包裹是为了关掉 T extends never 的分发（否则空联合时直接变 never）。

medium/296 就是这个套路，返回的是字符串形式的排列：

type Permutation<T extends string, Copy extends string = T> = [T] extends [
  never,
]
  ? ''
  : T extends any
  ? `${T}${'' extends Permutation<Exclude<Copy, T>>
      ? ''
      : ` ${Permutation<Exclude<Copy, T>>}`}`
  : never;

子集 / 幂集

"一个集合 A 的所有子集"。

type Subsets<T extends any[]> = T extends [infer F, ...infer R]
  ? Subsets<R> extends infer S
    ? S extends any[][]
      ? S[number] | [F, ...S[number]]
      : never
    : never
  : [[]];

// 稍简洁的版本：
type PowerSet<T extends any[], R extends any[] = []> = T extends [
  infer F,
  ...infer Rest,
]
  ? PowerSet<Rest, R> | PowerSet<Rest, [...R, F]>
  : [...R];

思路："对第一个元素，要 / 不要"两条路径分别递归。

参考题 medium/8987-Subsequence。

组合求和 / 两数之和

先构造所有可能组合，再筛：

// 两数之和 = N：遍历所有 (a, b)，保留 a + b = N 的
type TwoSum<T extends number[], N extends number> =
  // 伪代码，实际需要借助计数元组做加法
  T extends [infer A extends number, ...infer R extends number[]]
    ? R extends (infer B extends number)[]
      ? Add<A, B> extends N
        ? true
        : TwoSum<R, N>
      : false
    : false;

参考 hard/8804-两数之和。核心：先遍历所有对，再用 加减乘除 判等。

写这类题的通用节奏

1. 定边界：空集 / 单元素 / 空字符串返回什么？通常是 [] / '' / never；
2. 分发一层：要"对集合中每一个元素都尝试一次"，用 T extends any ? ... 或者头递归 T extends [infer F, ...infer R]；
3. 在分发结果里继续递归：注意递归入参，通常要从集合里删掉当前元素（联合用 Exclude，元组直接用 rest）；
4. 把递归结果拼回去：模板字符串 / [F, ...Rec] / 联合 |。

速查表

题型	核心动作
笛卡尔积	${A}${B} 模板或双重分发
C(n, k) 组合	对每一支"选 / 不选"
全排列	选一项作首，剩余递归
子集	同"选 / 不选"，但枚举所有大小
两数之和 / 多数之和	组合枚举 + 加法判等
字符全排列	字符串版的全排列模板

被谁用到

• 笛卡尔积：medium/3326-BEMstylestring。
• 组合：medium/8767-Combination, medium/4260-实现所有组合。
• 全排列：medium/296-实现全排列。
• 子集 / 子序列：medium/8987-Subsequence。
• 求和：hard/8804-两数之和, extreme/476-Sum。

心里把"边界 / 分发 / 递归 / 组装"这四步固化成模板，遇到排列组合题就能迅速反应。