TypeScript 类型挑战 04260 深度解析：用模板字面量类型实现 AllCombinations 全排列组合-平芜编程栈

示例工程

【免费下载链接】type-challenges

Collection of TypeScript type challenges with online judge

项目地址：https://gitcode.com/GitHub_Trending/ty/type-challenges

在 TypeScript 类型体操仓库 type-challenges 中，04260 是一道综合考察模板字面量类型、infer推断与联合类型分发的 Medium 级题目。本文将围绕题目说明 README.ja.md 展开，结合仓库配套的测试用例与工具类型实现，完整推导并给出一个可运行、可验证的AllCombinations<S>类型。读完你不仅能独立解出本题，还能掌握用类型系统做递归枚举与排列组合的通用套路。

题目速览：AllCombinations 是什么

根据 info.yml 的元数据，这道题的关键信息如下：

字段	值
难度	medium（日文版标注为「中級」）
标题	AllCombinations（日文标题：文字の組み合わせ）
作者	蛭子屋双六（sugoroku-y）
标签	template-literal、infer、union

题面要求（原文见 README.ja.md）：实现类型AllCombinations<S>，返回"使用S中的每个字符最多一次所能构成的所有字符串组合"（原文：指定された文字列に含まれる文字をそれぞれ最大で1度だけ使った文字列のすべての組み合わせ）。

题目给出的示例：

type AllCombinations_ABC = AllCombinations<'ABC'>; // should be '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' // | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'

从结果可以提炼出三条核心语义：

空字符串也是组合：结果始终包含''；
每个字符至多使用一次：因此不会出现'AA'、'AAB'这类重复使用字符的串；
顺序敏感，本质是"排列"而非"组合"：'AB'与'BA'是两条独立结果，说明该类型枚举的是"所有子集的全体全排列"。

用测试用例锁定输入输出的精确边界

本仓库为每道题都配套了template.ts与test-cases.ts。本题的起点模板 template.ts 只有一行占位：

type AllCombinations<S> = any

所有逻辑都需要由解题者补齐。而 test-cases.ts 给出了 5 个判定用例：

import type { Equal, Expect } from '@type-challenges/utils' type cases = [ Expect<Equal<AllCombinations<''>, ''>>, Expect<Equal<AllCombinations<'A'>, '' | 'A'>>, Expect<Equal<AllCombinations<'AB'>, '' | 'A' | 'B' | 'AB' | 'BA'>>, Expect<Equal<AllCombinations<'ABC'>, /* 共 16 个结果 */>>, Expect<Equal<AllCombinations<'ABCD'>, /* 共 65 个结果 */>>, ]

由此可以确认几个关键事实：

断言依赖Equal与Expect，二者来自@type-challenges/utils工具包，其实现位于 utils/index.d.ts。Expect<T extends true> = T负责把类型约束为true，而Equal利用"同一泛型函数在分别代入X、Y时返回类型是否一致"来判断两个类型严格相等：

export type Equal<X, Y> = (<T>() => T extends X ? 1 : 2) extends (<T>() => T extends Y ? 1 : 2) ? true : false

结果数量符合数学规律：设字符数为n，输出为所有子集的全排列之并，即Σ P(n, k)（k 从 0 到 n，P(n,k) = n!/(n-k)!）。因此n=1时 1+1=2 项，n=2时 1+2+2=5 项，n=3时 1+3+6+6=16 项，n=4时 1+4+12+24+24=65 项。这也解释了为什么'ABCD'一行的期望结果最长——它是 65 个字符串字面量的联合。

解题拆解（一）：StringToUnion —— 用模板字面量 + infer 拆分字符

模板字面量类型的核心能力，是在字符串上进行模式匹配与子串推断。第一步是把字符串S转成"字符联合类型"，它是后续所有递归枚举的燃料：

type StringToUnion<S extends string> = S extends `${infer C}${infer Rest}` ? C | StringToUnion<Rest> : never

原理说明：

`${infer C}${infer Rest}`是模板字面量推断：只要S非空，C就会被推断为首字符，Rest被推断为剩余部分；
联合分支C | StringToUnion<Rest>逐层"剥壳"，把每个字符并入联合；
基线分支：空字符串无法匹配该模板，返回never。

例如StringToUnion<'ABC'>会得到'A' | 'B' | 'C'。这是仓库内大量字符串处理题目的通用前置手法（例如00106-medium-trimleft、00298-medium-length-of-string等都是以模板字面量拆分字符串为起点的）。

解题拆解（二）：递归枚举 —— 映射类型 + Exclude 构成排列树

拿到字符联合U之后，问题就转化为"依次挑选下一个字符是谁"的递归枚举：

用映射类型遍历U中的每一个字符K；
一旦选定K，剩余可用的字符集合就是Exclude<U, K>；
递归地对剩余集合继续枚举，并把当前字符拼在前面：`${K}${AllCombinations<never, Exclude<U, K>>}`；
基线条件：当剩余字符为空（U为never）时，唯一结果是''。

这里有两个容易踩坑的细节：

never会短路裸条件类型：U extends never ? ... : ...这类裸露条件类型会因为never没有成员而整体变为never，导致递归无法终止。因此必须用元组包装[U] extends [never]来显式判断"已无剩余字符"的基线；
空串必须参与每一层递归：只有当子问题的结果包含''时，`${K}${''}`才能还原出单个字符K；最终在顶层再并上''，即可覆盖所有子集。

参考答案与逐层推演

综合以上思路，一份可运行、能通过全部 5 个用例的实现如下：

type StringToUnion<S extends string> = S extends `${infer C}${infer Rest}` ? C | StringToUnion<Rest> : never type AllCombinations< S extends string, U extends string = StringToUnion<S> > = [U] extends [never] ? '' // 基线：无可用字符 : '' | { [K in U]: `${K}${AllCombinations<never, Exclude<U, K>>}` }[U]

以AllCombinations<'ABC'>手动推演一遍：

首层U = 'A' | 'B' | 'C'，映射类型对三个字符分别展开：
- K = 'A'：'A' | AllCombinations<never, 'B' | 'C'>='A' | 'AB' | 'ABC' | 'AC' | 'ACB'
- K = 'B'：'B' | AllCombinations<never, 'A' | 'C'>='B' | 'BA' | 'BAC' | 'BC' | 'BCA'
- K = 'C'：'C' | AllCombinations<never, 'A' | 'B'>='C' | 'CA' | 'CAB' | 'CB' | 'CBA'
外层再并上''，恰好得到 16 个结果，与测试期望完全一致（联合类型本身无序，成员数量与内容一致即通过Equal断言）。