Subsequence

In this medium-level challenge, you'll implement a Subsequence type that returns a union of all possible subsequences of a given tuple, preserving the original element order.

[object Object]

type cases = [
  Expect<Equal<Subsequence<[1, 2]>, [] | [1] | [2] | [1, 2]>>,
  Expect<
    Equal<
      Subsequence<[1, 2, 3]>,
      [] | [1] | [2] | [1, 2] | [3] | [1, 3] | [2, 3] | [1, 2, 3]
    >
  >,
  Expect<
    Equal<
      Subsequence<[1, 2, 3, 4, 5]>,
      | []
      | [1]
      | [2]
      | [3]
      | [4]
      | [5]
      | [1, 2]
      | [1, 3]
      | [1, 4]
      | [1, 5]
      | [2, 3]
      | [2, 4]
      | [2, 5]
      | [3, 4]
      | [3, 5]
      | [4, 5]
      | [1, 2, 3]
      | [1, 2, 4]
      | [1, 2, 5]
      | [1, 3, 4]
      | [1, 3, 5]
      | [1, 4, 5]
      | 

Detailed Explanation

type Subsequence<T extends any[]> = T extends [infer F, ...infer Rest]
  ? [F, ...Subsequence<Rest>] | Subsequence<Rest>
  : []

How it works:

• We recursively decompose the tuple into its first element F and the remaining elements Rest.
• For each element, we create a union of two choices: include F in the subsequence ([F, ...Subsequence<Rest>]) or exclude it (Subsequence<Rest>).
• This binary include/exclude decision at each position generates all possible combinations while preserving the original order of elements.
• The base case returns [] (the empty tuple) when no elements remain, representing the empty subsequence.
• Because TypeScript distributes over union types in these positions, the recursive calls naturally expand into the full power set of subsequences. For example, with [1, 2], the expansion produces [1, 2] | [1] | [2] | [].

This challenge helps you understand recursive type-level combinatorics and union type generation and how to apply these concepts in real-world scenarios.