AllCombinations

In this medium-level challenge, you'll implement AllCombinations<S> that returns all possible permutations and combinations of characters from the string S, using each character at most once.

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

Detailed Explanation

type StringToUnion<S extends string> = S extends `${infer First}${infer Rest}`
  ? First | StringToUnion<Rest>
  : never
 
type Combinations<U extends string, S extends string = U> =
  S extends S
    ? '' | `${S}${Combinations<Exclude<U, S>>}`
    : never
 
type AllCombinations<S extends string> = Combinations<StringToUnion<S>>

How it works:

• StringToUnion<S> converts a string like 'ABC' into a union of its individual characters: 'A' | 'B' | 'C'
• Combinations<U, S> is the core recursive type that generates all permutations. The parameter S defaults to U and is used to distribute over the union
• S extends S is a distributive conditional type trick that iterates over each member of the union S
• For each character S, it prepends that character to the result of Combinations<Exclude<U, S>>, which recursively generates combinations from the remaining characters (excluding the current one)
• The '' in the union ensures the empty string is always included, which also serves as the base case when there are no more characters to combine
• AllCombinations<S> ties it together by first converting the string to a union, then passing it to Combinations

This challenge helps you understand distributive conditional types, recursive type generation, and template literal types, and how to apply these concepts in real-world scenarios.