For example:

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

Solution by adultlee #35183

type StringToUnion<S extends string> = S extends `${infer f}${infer rest}` ? f | StringToUnion<rest> : never;
type AllCombinations<S extends string, T extends string = StringToUnion<S>> = [T] extends [never] ? '' : '' | {
  [k in T]: `${k}${AllCombinations<never, Exclude<T, k>>}`
}[T]

Solution by wendao-liu #35067

由题意可知我们的目标是将一个字符串进行拆解，然后形成不限制数量的各种 自由组合。

很明显我们需要一个能够将字符串中的每个字符单独拆分，并最终将所有的拆分结果形成一个联合类型的工具函数：

type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : ''

利用 infer F 来获取字符串的首个字符，然后递归字符串的剩余部分 infer R，最终通过 ｜ 将后续递归的结果形成联合类型。

看看效果：

type Test = StringToUnion<'ABC'>
// Test = '' | 'A' | 'B' | 'C'

此时已经对字符串进行了初步的拆解，这就相当于搭积木有了基本的积木块，但是还需要去组合这些积木块才能达成目标。

抛开整个问题全貌，先思考这样一个问题：各种组合是如何拼接出来的？

下面举例 BAC 的组合过程：

首先，需要在原始的字符串 ABC 中将 B 去掉形成 AC，然后拿出拆解出来的字符 B 拼接在 AC 的前面最终形成

组合 BAC，其余的组合也都是如此实现，但是如何实现呢？

先别急，在正式解决这个问题之前，先来实现一个从字符串中去掉指定字符的工具函数：

type ExcludeString<S, T extends string> = S extends `${infer A}${T}${infer B}` ? `${A}${B}` : S

通过 infer A，T， infer B 来匹配目标字符串 T，匹配成功就返回除 T 之外的内容，否则直接返回原字符串

看看效果：

type Test = ExcludeString<'ABC', 'B'>
// Test = 'AC'

太棒了，这和上面思考过程的效果一样！

回到题目，此时已经有了工具函数可以使用，我们可以先将原始字符串 S 的每一个字符转换为联合类型 T 从而获取最基本的 素材：

type AllCombinations<S extends string, T extends string = StringToUnion<S>> = any

这时你一定想起了在前面的类型体操 029 medium permutation 中，热门答案详细解释了如何通过 T extends T的方式来在条件语句中 展开遍历 一个联合类型 传送门

是的，此时就需要利用这个特性来遍历联合类型 T，从而实现对展开后的联合类型 T 中每个类型的处理

此时代码变成：

type AllCombinations<S extends string, T extends string =
  StringToUnion<S>> = T extends T ? /*do smth*/  : S

type Result = AllCombinations<'ABC'>

// T = '' | 'A' | 'B' | 'C' 注意此处展示的是 T 的类型，Result 后面再说

上面我们提到了组合的形成过程，先来尝试从原字符串中去掉一个字符看看效果，改变 do smth 部分：

type AllCombinations<S extends string, T extends string =
  StringToUnion<S>> = T extends T ? `${ExcludeString<S, T>}`  : S

type Result = AllCombinations<'ABC'>

// Result = 'ABC' | 'BC' | 'AB' | 'AC'

因为 T = '' | 'A' | 'B' | 'C'，将联合类型的每个分支分别代入 ExcludeString 就不难理解为什么结果是 'ABC' | 'BC' | 'AB' | 'AC'

相信你此时一定灵光一闪：将结果中的 'ABC' | 'BC' | 'AB' | 'AC' 再次作为参数传入 AllCombinations 进行递归，不就能得到最后的结果了吗？

来尝试一下，将代码修改为：

type AllCombinations<S extends string, T extends string =
  StringToUnion<S>> = T extends T ? `${AllCombinations<ExcludeString<S, T>>}`  : S

type Result = AllCombinations<'ABC'>

// ERROR: 类型实例化过深，且可能无限

哈？why？

别慌，我们来思考下无限递归是如何出现的

先看联合类型 T 的第一个分支，即 T 为 ''，此时代码执行情况为：

// 第一次执行
AllCombinations<ExcludeString<'ABC', ''>>

ExcludeString<'ABC', ''> 的执行结果为 ABC

接下来，ABC 作为参数传入下一次递归中：

// 递归
AllCombinations<ExcludeString<'ABC', ''>>

原来如此，当 T 的类型为 '' 时，代码进入了无限递归。现在尝试来排除这种情况：

type AllCombinations<S extends string, T extends string =
  StringToUnion<S>> = T extends T ? `${T extends '' ? T : AllCombinations<ExcludeString<S, T>>}`  : S

type Result = AllCombinations<'ABC'>

// Result = "" | "ABC" | "A" | "BC" | "B" | "C" | "AB" | "CB" | "AC" | "ACB" | "CA" | "BA" | "BAC" | "BCA" | "CAB" | "CBA"

此时题目中的测试用例已经全部通过，目标达成，此刻代码全貌：

type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : ''

type ExcludeString<S, T extends string> = S extends `${infer A}${T}${infer B}` ? `${A}${B}` : S

type AllCombinations<S extends string, T extends string = StringToUnion<S>> = T extends T ? `${T}${T extends '' ? T : AllCombinations<ExcludeString<S, T>>}` : S

当然，这种方式并不是最巧妙的方式，但希望通过展开整个思考过程的方式能够帮助到有需要的人

Solution by jzllove9 #34797

type StringToUnion<S extends string> = S extends `${infer R}${infer rest}` ? R | StringToUnion<rest> : S
type AllCombinations<S extends string, T extends string = StringToUnion<S>, U extends string = T> = 
S extends `${any}${infer rest}` ? U extends U ?
`${U}${AllCombinations<rest, U extends '' ? T : Exclude<T, U>>}` : never : ''

Solution by ouzexi #34068

// your answers
type StringToUnion<T extends string> = T extends `${infer A}${infer R}` ? A | StringToUnion<R> : never

type AllCombinations<S extends string, K extends string = StringToUnion<S>, U extends string = K> =
  [K] extends [never] ? '' : 
    K extends K ?
    '' | `${K}${AllCombinations<Exclude<U, K>>}` 
    : never

Solution by heyuelan #33842

type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
type AllCombinations<
  S extends string,
  T extends string = StringToUnion<S>,
  U extends string = T,
> = S extends `${infer F}${infer R}`
  ? U extends U
    ? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
    : never
  : ''

Solution by MyeonghoonNam #31162

type ToLetters<S extends string> =
  S extends `${infer F}${infer R}`
    ? F | ToLetters<R>
    : never

type AllCombinations<
  S extends string,
  L extends string = '' | ToLetters<S>,
  U extends string = L
> =
  L extends U
    ? '' | `${L}${AllCombinations<never, Exclude<U, L>>}`
    : never

Solution by sbr61 #30134

type StringToArray<S, L extends string[] = []> = S extends `${infer A}${infer B}` ? [A, ...StringToArray<B, L>] : L

type Combination<T extends string[], All = T[number], Item = All> = Item extends string ? Item | `${Item}${Combination<[], Exclude<All, Item>>}` : never

type AllCombinations<S> = '' | Combination<StringToArray<S>>

Solution by tclxshunquan-wang #29848

type StrToUnion<T extends string> = T extends `${infer L}${infer R}`
  ? L | StrToUnion<R>
  : T;
  
type AllCombinations<
  S extends string,
  U extends string = StrToUnion<S>,
  All extends string = U
> = U extends U ? U | `${U}${AllCombinations<S, Exclude<All, U>>}` : never;

Solution by DoubleWoodLin #28835

type StrToUnion<T extends string> = T extends `${infer L}${infer R}`
  ? L | StrToUnion<R>
  : T;

type AllCombinations<S extends string, U extends string = StrToUnion<S>> = [
  U
] extends [never]
  ? ""
  :
      | {
          [K in U]: `${K}${AllCombinations<never, Exclude<U, K>>}`;
        }[U]
      |"";

Solution by DoubleWoodLin #28738

// your answers
type StrToUnion<S extends string, R = never> = S extends `${infer F}${infer L}` ? StrToUnion<L, R | F> : R;

type AllCombinations<S extends string, U extends string = StrToUnion<S>> = [U] extends [never] ? '' : '' | { 
  [K in U]: `${K}${AllCombinations<never, Exclude<U, K>>}`
}[U];

Solution by CheolMinBae #27241

This is an interesting approach that I tried that did not work. I have not yet taken a look at the other solutions but I suspect they make utility of converting strings to unions. I tried to do it in the string space.

I also created a debugging function in the form of a generic type that shows the permutations (i.e. combinations) which were left out by my implementation.

namespace Utilities {
  export type C<S extends string> =
    S extends `${infer First}${infer Rest}` ?
      First | C<Rest> | `${C<Rest>}${First}` | `${First}${C<Rest>}` : ""
}

type AllCombinations<S extends string> = "" | Utilities.C<S>

type DebugAllCombinations<A extends string, B extends string> =
  B extends AllCombinations<A> ? never : B

// this evaluates to "BAC" | "CAB"
type difference1 = DebugAllCombinations<'ABC', '' | 'A' | 'B' | 'C' | 'AB' | 'AC' | 'BA' | 'BC' | 'CA' | 'CB' | 'ABC' | 'ACB' | 'BAC' | 'BCA' | 'CAB' | 'CBA'>
// this evaluates to "BAC" | "CAB" | "BAD" | "CAD" | ...
type difference2 = DebugAllCombinations<'ABCD', '' | 'A' | 'B' | 'C' | 'D' | 'AB' | 'AC' | 'AD' | 'BA' | 'BC' | 'BD' | 'CA' | 'CB' | 'CD' | 'DA' | 'DB' | 'DC' | 'ABC' | 'ABD' | 'ACB' | 'ACD' | 'ADB' | 'ADC' | 'BAC' | 'BAD' | 'BCA' | 'BCD' | 'BDA' | 'BDC' | 'CAB' | 'CAD' | 'CBA' | 'CBD' | 'CDA' | 'CDB' | 'DAB' | 'DAC' | 'DBA' | 'DBC' | 'DCA' | 'DCB' | 'ABCD' | 'ABDC' | 'ACBD' | 'ACDB' | 'ADBC' | 'ADCB' | 'BACD' | 'BADC' | 'BCAD' | 'BCDA' | 'BDAC' | 'BDCA' | 'CABD' | 'CADB' | 'CBAD' | 'CBDA' | 'CDAB' | 'CDBA' | 'DABC' | 'DACB' | 'DBAC' | 'DBCA' | 'DCAB' | 'DCBA'>

Solution by diraneyya #27154

type StringToUnion<S extends string> = S extends `${infer F}${infer Rest}` ? F | StringToUnion<Rest> : S
// type ProcessUnion<S extends string, Ret extends string = '', Acc extends string = S>
//   = [ S ] extends [ never ] ? never
//     : Acc extends any
//       ? Ret | Acc | ProcessUnion<Exclude<S, Acc>, `${Ret}${Acc}`>
//       : never
// type AllCombinations<S extends string> = ProcessUnion<StringToUnion<S>>

type AllCombinations<S extends string, Acc extends string = StringToUnion<S>>
  = [ Acc ] extends [ never ] ? ''
    : '' | { [ C in Acc ]: `${C}${AllCombinations<'', Exclude<Acc, C>>}` }[Acc]

Solution by tokyo9pm #26781

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

type Permutation<T, U=T> = [T] extends [never] ? [] : T extends U ? [T, ...Permutation<Exclude<U, T>>] : []

type PermutationComb<T, U=T> = (T extends U ? PermutationComb<Exclude<U, T>> : never) | Permutation<U>

type ArrToString<T> = T extends [] ? '' : T extends [infer F extends string, ...infer Rest] ? `${F}${ArrToString<Rest>}`  : never

type AllCombinations<S extends string> = ArrToString<PermutationComb<StringToUnion<S>>>

Solution by enochjs #25970

type StringToUnion<T extends string, R extends string[] = []> = T extends `${infer K}${infer U}`
  ? StringToUnion<U, [...R, K]>
  : R[number] | "";


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

type AllCombinations<S extends string> = Combination<StringToUnion<S>>;

Solution by yungo1846 #25640

// your answers
type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
  ? A | StringToUnion<Rest>
  : "";

type Combinations<T extends string, U = T> = U extends T
  ? U | `${U}${Combinations<Exclude<T, U>>}`
  : never;
  
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;

Solution by kiki-zjq #25225

4260 - AllCombinations

AllCombinations will make you want to cry when you read the description, but the solution is actually pretty easy (so long as you can launch your brain into a recursive 4th dimension).

🎥 Video Explanation

🔢 Code

// ============= Test Cases =============
import type { Equal, Expect } from "./test-utils";

type A1 = AllCombinations<"">;
type B1 = "";
type C1 = Expect<Equal<A1, B1>>;

type A2 = AllCombinations<"A">;
type B2 = "" | "A";
type C2 = Expect<Equal<A2, B2>>;

type A3 = AllCombinations<"AB">;
type B3 =
  | "" | "A" | "B"
  | "AB" | "BA"
;
type C3 = Expect<Equal<A3, B3>>;

type A4 = AllCombinations<"ABC">;
type B4 = 
  | ""
  | "A"
  | "B"
  | "C"
  | "AB" | "AC"
  | "BA" | "BC"
  | "CA" | "CB"
  | "ABC" | "ACB"
  | "BAC" | "BCA"
  | "CAB" | "CBA"
;
type C4 = Expect<Equal<A4, B4>>;

type A5 = AllCombinations<"ABCD">;
type B5 =
  | ""
  | "A"
  | "B"
  | "C"
  | "D"
  | "AB" | "AC" | "AD"
  | "BA" | "BC" | "BD"
  | "CA" | "CB" | "CD"
  | "DA" | "DB" | "DC"
  | "ABC" | "ABD" | "ACB" | "ACD" | "ADB" | "ADC"
  | "BAC" | "BAD" | "BCA" | "BCD" | "BDA" | "BDC"
  | "CAB" | "CAD" | "CBA" | "CBD" | "CDA" | "CDB"
  | "DAB" | "DAC" | "DBA" | "DBC" | "DCA" | "DCB"
  | "ABCD" | "ABDC" | "ACBD" | "ACDB" | "ADBC" | "ADCB"
  | "BACD" | "BADC" | "BCAD" | "BCDA" | "BDAC" | "BDCA"
  | "CABD" | "CADB" | "CBAD" | "CBDA" | "CDAB" | "CDBA"
  | "DABC" | "DACB" | "DBAC" | "DBCA" | "DCAB" | "DCBA"
;
type C5 = Expect<Equal<A5, B5>>;

// ============= Your Code Here =============
// previous challenge: 43
type Exclude<T, U> = T extends U ? never : T;

// previous challenge: 1042
type IsNever<T> = [T] extends [never] ? true : false;

// previous challenge: 531
type StringToUnion<T> =
  T extends `${infer Head}${infer Tail}`
  ? Head | StringToUnion<Tail>
  : never;

type AllCombinations<
  S,
  Acc extends string = StringToUnion<S>
> =
  IsNever<Acc> extends true
  ? ""
  : "" | {
    [Combo in Acc]:
      `${
        Combo
      }${
        AllCombinations<
          never,
          Exclude<Acc, Combo>
        >
      }`
  }[Acc];

// ============== Alternatives ==============
type StringToUnion<S extends string> =
  S extends `${infer Head}${infer Tail}`
  ? Head | StringToUnion<Tail>
  : S; // this variant doesn't return never
type Combination<A extends string, B extends string> =
  | A
  | B
  | `${A}${B}`
  | `${B}${A}`;
type UnionCombination<
  A extends string,
  B extends string = A
> =
  A extends B
  ? Combination<A, UnionCombination<Exclude<B, A>>>
  : never;
type AllCombinations<S extends string> =
  UnionCombination<StringToUnion<S>>

type AllCombinations<
  S extends string,
  Acc extends string = ''
> =
  S extends `${infer Head}${infer Tail}`
  ?
    | `${Head}${AllCombinations<`${Acc}${Tail}`>}`
    | AllCombinations<Tail, `${Acc}${Head}`>
  : '';

➕ More Solutions

For more video solutions to other challenges: see the umbrella list! https://github.com/type-challenges/type-challenges/issues/21338

Solution by dimitropoulos #24325

type SplitTo<T extends string> = T extends `${infer F}${infer R}` ? F | SplitTo<R> : ``;
type UnionComb<T extends string, U = T> = U extends T ? U | `${U}${UnionComb<Exclude<T, U>>}` : never;

type AllCombinations<S extends string> = UnionComb<SplitTo<S>>;

Solution by E-uler #23945

type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
  ? A | StringToUnion<Rest>
  : "";

type Combinations<T extends string, U = T> = U extends T
  ? U | `${U}${Combinations<Exclude<T, U>>}`
  : never;

type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;

Solution by snakeUni #22887

// your answers
type Combination<A extends string, B extends string> = A | B | `${A}${B}` | `${B}${A}`
type StringToUnion<Str extends string> = Str extends `${infer F}${infer Rest}` ? F | StringToUnion<Rest> : never;
type InAllCombinations<A extends string, B extends string = A> = A extends A ? Combination<A, AllCombinations<Exclude<B, A>>> : never;
type AllCombinations<S extends string> = InAllCombinations<StringToUnion<S>> | ''

Solution by jxhhdx #22718

// eg. "abc" => "a" | "b" | "c"
type StringToCharsUnion<S, L = never> =
  S extends `${infer F}${infer R}` ? StringToCharsUnion<R, L | F> : L;

// answer
type InnerAllCombinations<S, Path extends string, RU = never, SS = S> = 
  [S] extends [never]
    ? RU | Path
    : S extends string // Distributive Conditional Types
      ? InnerAllCombinations<Exclude<SS, S>, `${Path}${S}`, RU | Path>
      : RU;

type AllCombinations<S extends string> =
  InnerAllCombinations<StringToCharsUnion<S>, "">;

Solution by coderyoo1 #22634

type StringToUnion<S extends string> = S extends `${infer A}${infer Rest}`
  ? A | StringToUnion<Rest>
  : "";

type Combinations<T extends string, U = T> = U extends T
  ? U | `${U}${Combinations<Exclude<T, U>>}`
  : never;

type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;

Solution by codeisneverodd #22206

type AllCombinations<S extends string, U = '', U1 = U> =
  S extends `${infer A}${infer Rest}`
    ? AllCombinations<Rest, U | A>
    : U extends string
      ? U | `${U}${AllCombinations<'', Exclude<U1, U>>}`
      : ''

Solution by drylint #22154

type ToUnion<T extends string> = T extends `${infer F}${infer R}` ? F | ToUnion<R> : never;
type AllCombinationsByTypes<T extends string, U extends string = T> = [T] extends [never] ? ''
  : T extends string ? `${T | ''}${AllCombinationsByTypes<Exclude<U, T>>}` : '';
type AllCombinations<T extends string> = AllCombinationsByTypes<ToUnion<T>>

Solution by yeyunjianshi #22014

type AllCombinations<S, Character extends string = "", CharUnion extends string = Character> =
S extends `${infer First}${infer Remainder extends string}`
  ? AllCombinations<Remainder, Character | First>
  : Character extends "" ? "" :
    `${Character}${AllCombinations<"", CharUnion extends Character ? "" : CharUnion>}`;

Solution by gaac510 #21187

// your answers
// copy
type StringToUnion<S> = S extends `${infer F}${infer R}` ? F | StringToUnion<R> : S
type AllCombinations<
  S extends string,
  T extends string = StringToUnion<S>,
  U extends string = T,
> = S extends `${infer F}${infer R}`
  ? U extends U
    ? `${U}${AllCombinations<R, U extends '' ? T : Exclude<T, U>>}`
    : never
  : ''

Solution by Quanzhitong #19818

Well, after reviewing the solution list, I found most solutions are the version or variantions of String2Union. This solution may provide a new branch of idea for us.

Simply, by just describing the algorithm, we get the anwser.

// util, get first character from an string
type Head<T extends string> = T extends `${infer First}${any}` ? First : never

// C is the current character to be handled in S
type AllCombinations<S extends string, C extends string = ''> = 
  S extends '' ? '' : // edge case, fast return
  C extends ''  // is this the first time to handle S?
    ? AllCombinations<S, Head<S>>                  // if so, we start handling it from its first character
    : S extends `${infer Left}${C}${infer Right}`  // else, we match S into 3 parts: Left, C, Right
      // in the view of algorightm of combination, the final result is acctually the union of following parts ...
      ? AllCombinations<`${Left}${Right}`>            // 1. the combinations of the rest characters without current character
        | `${C}${AllCombinations<`${Left}${Right}`>}` // 2. the combinations of the rest characters without current character, prefixed by current character
        | AllCombinations<S, Head<Right>>             // 3. the combinations of the all characters, with the next character to be handled
      : never

playground

Solution by zhaoyao91 #19690

// 将字符串转化为`Union`类型
type StringToUnion<S extends string> = S extends `${infer F}${infer R}`
  ? F | StringToUnion<R>
  : "";

type Combinations<T extends string, U = T> = U extends T
  ? U | `${U}${Combinations<Exclude<T, U>>}`
  : never;
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>;

Solution by CaoXueLiang #18249

type StringToUnion<T extends string> = T extends `${infer F}${infer R}` ? F | StringToUnion<R> : ''

type Combinations<T extends string, U = T> = U extends T
  ? U | `${U}${Combinations<Exclude<T, U>>}`
  : never

type AllCombinations<S extends string> = Combinations<StringToUnion<S>>

Solution by milletlovemouse #17626

type StrToUnion<S extends string> = S extends `${infer F}${infer R}` ? F | StrToUnion<R> : never;

type Pair<S extends string, T extends string = S> =
  [S] extends [never]
    ? ''
    : S extends string
        ? `${S}${Pair<Exclude<T, S>>}` | Pair<Exclude<T, S>>
        : never

type AllCombinations<S extends string> = Pair<StrToUnion<S>>

Solution by YOUNGmaxer #17548