Two Sum

Two Sum is the classic interview warm-up: given a tuple of integers nums and an integer target, return true if two numbers in the tuple add up to target. This version runs entirely in the type system, where there is no + and no ===, so even addition has to be rebuilt from scratch. As in the original LeetCode problem, the two numbers must sit at different positions, but the same value may be used twice if it appears twice.

For example

type sum1 = TwoSum<[3, 2, 4], 6> // true
type sum2 = TwoSum<[2, 7, 11, 15], 15> // false

You'll combine two staples of advanced TypeScript, addition via tuple lengths and pairwise recursion over a tuple, into a complete type-level algorithm.

type sum1 = TwoSum<[3, 2, 4], 6> // true
type sum2 = TwoSum<[2, 7, 11, 15], 15> // false

Detailed Explanation

The full solution:

type Tuple<N extends number, R extends unknown[] = []> = R['length'] extends N
  ? R
  : Tuple<N, [...R, unknown]>
 
type Add<A extends number, B extends number> = [
  ...Tuple<A>,
  ...Tuple<B>,
]['length']
 
type HasPartner<
  A extends number,
  T extends number[],
  U extends number,
> = T extends [infer B extends number, ...infer Rest extends number[]]
  ? Add<A, B> extends U
    ? true
    : HasPartner<A, Rest, U>
  : false
 
type TwoSum<T extends number[], U extends number> = T extends [
  infer First extends number,
  ...infer Rest extends number[],
]
  ? HasPartner<First, Rest, U> extends true
    ? true
    : TwoSum<Rest, U>
  : false

At runtime you'd write two nested loops (or a hash map). At the type level, each loop becomes a recursive type, so the solution is two recursions, one nested inside the other, on top of a tiny arithmetic library. It reads best bottom-up.

Teaching the type system to add

TypeScript types have no +, but tuples know their own length as a literal type. So numbers can be represented as tuples and added by concatenation.

• Tuple<N> converts a number into a tuple with N elements by pushing unknowns one at a time until R['length'] extends N succeeds. Tuple<3> is [unknown, unknown, unknown].
• Add<A, B> spreads both tuples into one and reads the combined length:

[object Object]

This unary-numbers trick only works for non-negative integers of modest size, which is the territory these test cases live in.

The inner loop: HasPartner

HasPartner<A, T, U> answers: does any element of T complete A to the target U? It walks the tuple front-first with the pattern [infer B extends number, ...infer Rest extends number[]]: B is the current candidate, Rest is everything after it. The inline extends number constraints on infer keep the captured types usable by Add, which requires number arguments.

For each candidate it checks Add<A, B> extends U. Since Add produces an exact literal like 6 and U is a single literal too, extends acts as an equality test here (against a union it would be a membership test instead). On a hit it short-circuits to true; otherwise it recurses down the rest; an empty tuple means no partner exists and the result is false.

The outer loop: TwoSum

TwoSum picks each element in turn as First and asks HasPartner<First, Rest, U>, searching only the rest of the tuple, never the element itself. That single detail encodes the "two different indices" rule:

• TwoSum<[3, 3], 6> is true: the first 3 finds the second 3 in its Rest.
• TwoSum<[1, 2, 3], 6> is false: when First is 3, Rest is []; the solution never pairs 3 with itself.

If the inner search fails, the outer recursion drops First and tries the next element; an exhausted tuple yields false. Effectively you're checking every pair (i, j) with i < j, the honest O(n²) version of Two Sum.

Tracing TwoSum<[3, 2, 4], 6>:

// First = 3, Rest = [2, 4]: 3+2 = 5, 3+4 = 7 → no partner
// First = 2, Rest = [4]:    2+4 = 6 → true

Edge cases the tests cover

• TwoSum<[3, 3], 6> → true versus TwoSum<[1, 2, 3], 6> → false: duplicated values are fair game, self-pairing is not. Both fall out of searching only Rest.
• TwoSum<[1, 2, 3], 0> and TwoSum<[1, 2, 3], 1> → false: targets smaller than any possible pair fail cleanly because Add never matches, not because of any special guard.
• TwoSum<[3, 2, 0], 2> → true: zero participates in sums like any other value (2 + 0 = 2), confirming Tuple<0> correctly produces the empty tuple.
• TwoSum<[2, 7, 11, 15], 15> → false: a target that is itself an element but not a pairwise sum. A trap if you were tempted to check membership instead of addition.

If you enjoyed this, try the same decomposition on other array problems: once you have Add and head/tail recursion in your toolkit, a surprising amount of LeetCode is expressible in pure types.