Type Challenges: 04260-medium-nomiwase Solution

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

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

Solution by micaiguai #37373

type AllCombinations<
  S extends string,
  T extends string = S
> = S extends `${infer First}${infer Rest}`
  ?
      | `${First}${AllCombinations<Rest>}`
      | (`${Rest}${First}` extends T
          ? ""
          : AllCombinations<`${Rest}${First}`, T>)
  : "";

The general idea is as follows:

By sequentially moving the first character to the end of the string, we ensure that all possible combinations are generated.

The termination condition for the recursive calls is determined by checking if the result of the next operation is the same as the original string.

Solution by Barrenboat #37315

// your answers
type StringToArray<S extends string> = S extends `${infer first}${infer Rest}` ? [first, ...StringToArray<Rest>] : [] 

type AllCombinations<S extends string> = S extends '' ? '' : '' | Combination<StringToArray<S>>

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

Solution by duanlvxin #36711

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

type AllCombinations<
  S extends string,
  U extends string = StringToUnion<S>,
  UU extends string = U
> = U extends ''
  ? ''
  : U extends U
  ? `${U}${AllCombinations<'', Exclude<'' | UU, U>>}`
  : 'hello world !!!'

//看了 https://github.com/type-challenges/type-challenges/issues/11027 后改的代码
type AllCombinations<
  S extends string,
  U = StringToUnion<S>,
  UU = U
> = U extends string
  ? U | `${U}${AllCombinations<'', Exclude<UU, U>>}`
  : never

Solution by goddnsgit #36211

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

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

type AllCombinations<S extends string> = 
  S extends ''
    ? ''
    : Permutation<StringToUnion<S>>;

Solution by gangnamssal #35695

Implement type AllCombinations ~~that return all combinations of strings which use characters from S at most once.~~

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 goni-ssi #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