8804 - Two Sum (with explanation, new test case)

[MajorLift]

// Iterate over T 
// -> If current element CURR > TARGET and TARGET - CURR exists in the remainder of T, return true.
// -> Else, recursively call TwoSum over remainder of T.
// -> If iteration is completed, return false.
type TwoSum<
  T extends number[], 
  TARGET extends number,
  CURR extends number = T[0],
  NEXT extends number[] = Shift<T>,
  RESULT extends boolean = T extends [] ? false
    : LessThan<TARGET, CURR> extends true ? TwoSum<NEXT, TARGET>
    : Subtract<TARGET, CURR> extends NEXT[number] ? true
      : TwoSum<NEXT, TARGET>
> = RESULT;

/** Helpers */
// new Array(N).fill(T)
type Repeat<N extends number, T extends any = null, M extends T[] = []> = 
  M["length"] extends N ? M : Repeat<N, T, [T, ...M]>;

// If A >= B, return A - B. Else, return never.
type Subtract<A extends number, B extends number> = 
  Repeat<A> extends [...Repeat<B>, ...infer Rest] 
    ? Rest["length"]
    : never;

type LessThan<T extends number, U extends number> = 
  Equal<T, U> extends true ? false
    : Subtract<T, U> extends never ? true : false;

type Shift<T extends any[], N extends number = 1> = 
  N extends 0 ? T 
    : T extends [infer _, ...infer Rest]
      ? Shift<Rest, Subtract<N, 1>>
      : [];

type TwoSumNewTests = [
  // The following incorrect solution passes all other test cases:
  // ... ? Subtract<U, E> extends never
  //       ? false ...
  Expect<Equal<TwoSum<[3, 2, 0], 2>, true>>
];

type SubtractTests = [
  Expect<Equal<Subtract<0, 0>, 0>>,
  Expect<Equal<Subtract<1, 0>, 1>>,
  Expect<Equal<Subtract<2, 1>, 1>>,
  Expect<Equal<Subtract<1, 2>, never>>,
];

type RepeatTests = [
  Expect<Equal<Repeat<0>, []>>,
  Expect<Equal<Repeat<3>, [null, null, null]>>,
  Expect<Equal<Repeat<3, "1">, ["1", "1", "1"]>>,  
];