AllCombinations

Challenge

Implement type AllCombinations<S> 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

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

type AllCombinations<
  S extends string,
  U extends string = StringToUnion<S>,
  P extends string = U
> =
  | U
  | (P extends any
      ? `${P}${AllCombinations<S, U extends P ? never : U>}`
      : never);

References