/*
Two Sum from leetcode: {@link https://leetcode.com/problems/two-sum/}
*/
type OptionalPropertyNames<T> = {
[K in keyof T]: undefined extends T[K] ? K : never;
}[keyof T];
type SpreadProperties<L, R, K extends keyof L & keyof R> = {
[P in K]: L[P] | Exclude<R[P], undefined>;
};
type Id<T> = { [K in keyof T]: T[K] };
type ConstructObject<T extends number> = {
[K in T]: true;
};
export type Equal<Left, Right> = (<T>() => T extends Left ? true : false) extends <T>() => T extends Right
? true
: false
? true
: false;
type Spread<L, R> = Id<
Pick<L, Exclude<keyof L, keyof R>> &
Pick<R, Exclude<keyof R, OptionalPropertyNames<R>>> &
Pick<R, Exclude<OptionalPropertyNames<R>, keyof L>> &
SpreadProperties<L, R, OptionalPropertyNames<R> & keyof L>
>;
type BuildTuple<N extends number, P extends any[] = []> = P["length"] extends N
? P
: BuildTuple<N, [...P, 1]>;
type Length<A extends any[]> = A["length"];
type Subtract<A extends number, B extends number> = BuildTuple<A> extends [
...infer U,
...BuildTuple<B>
]
? Length<U>
: never;
type IsArrayEqual<A extends any[], P > = A extends [infer Head, ...infer Tail] ? Equal<Head, P> extends true ? true : IsArrayEqual<Tail, P> : false
type TwoSum<
A extends number[],
Target extends number,
H extends Record<number, true> = {},
S extends number[][] = []
> = A extends [infer Head extends number, ...infer Tail extends number[]]
? Equal<H[Subtract<Target, Head>], true> extends true
? IsArrayEqual<S, [Subtract<Target, Head>, Head]> extends true ?
TwoSum<Tail, Target, H , S>
: TwoSum<Tail, Target, H , [...S, [Subtract<Target, Head>, Head]]>
: TwoSum<Tail, Target, Spread<H, ConstructObject<Head>>, S>
: Length<S> extends 1 ? S[0] : Length<S> extends 0 ? `No numbers add up to ${Target}`: S;
type ExampleOne = TwoSum<[ 1, 5, 3, 63, 4, 3, 6, 5, 3, 4, 123, 2, 5, 3], 8>;
// ^?
type ExampleTwo = TwoSum<[ 13, 64, 21, 9, 12, 6, 2, 5], 11>;
// ^?
type ExampleThree = TwoSum<[10,43,53,12,4,2,412,5,512,412,123,12,312,321,4], 424>
// ^?
type ExampleFour = TwoSum<[10,43,53,12,4,2,412,5,512,412,123,12,312,321,4], 433>
// ^?