Combination

In this medium-level challenge, you'll implement Combination<T> which takes an array of strings and generates all possible permutations and combinations of those strings joined by spaces.

// expected to be `"foo" | "bar" | "baz" | "foo bar" | "foo bar baz" | "foo baz" | "foo baz bar" | "bar foo" | "bar foo baz" | "bar baz" | "bar baz foo" | "baz foo" | "baz foo bar" | "baz bar" | "baz bar foo"`
type Keys = Combination<['foo', 'bar', 'baz']>

type cases = [
  Expect<
    Equal<
      Combination<['foo', 'bar', 'baz']>,
      | 'foo'
      | 'bar'
      | 'baz'
      | 'foo bar'
      | 'foo bar baz'
      | 'foo baz'
      | 'foo baz bar'
      | 'bar foo'
      | 'bar foo baz'
      | 'bar baz'
      | 'bar baz foo'
      | 'baz foo'
      | 'baz foo bar'
      | 'baz bar'
      | 'baz bar foo'
    >
  >,
  Expect<
    Equal<
      Combination<['apple', 'banana', 'cherry']>,
      | 'apple'
      | 'banana'
      | 'cherry'
      | 'apple banana'
      | 'apple cherry'
      | 'banana apple'
      | 'banana cherry'
      | 'cherry

Detailed Explanation

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

How it works:

• The type converts the input array T into a union of its members using T[number], stored in U. The parameter S defaults to U and is used for distributive iteration
• S extends S is a distributive conditional type trick that iterates over each member of the union S
• For each string S, it produces two results: the string itself (S), and that string followed by a space and all combinations of the remaining strings (${S} ${Combination<[], Exclude<U, S>>})
• Exclude<U, S> removes the current string from the available set, ensuring each string is used at most once per combination
• The recursion naturally terminates when Exclude<U, S> results in never, at which point the template literal with never produces never and is eliminated from the union
• The first parameter T is passed as [] in recursive calls since only the union U matters after the initial conversion

This challenge helps you understand distributive conditional types and recursive union generation for permutation problems, and how to apply these concepts in real-world scenarios.