8987. Subsequence

문제

Given an array of unique elements, return all possible subsequences.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

type A = Subsequence<[1, 2]> // [] | [1] | [2] | [1, 2]

cases

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] >>,
]

문제 링크

정답

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

type AddValue<T extends any[], V> = T extends T
  ? T | [V, ...T]
  : never

풀이

조건

1. 모든 부분집합을 출력한다.

해설

먼저 모든 요소를 출력하는 타입을 만든다.

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

그 후 값을 집어넣는 타입을 만든다.

type AddValue<T extends any[], V> = T | [V, ...T]

Union 타입이므로, Union의 모든 요소에 접근하여 값을 집어 넣을 수 있도록 수정한다.

type AddValue<T extends any[], V> = T extends T
  ? T | [V, ...T]
  : never

두 타입을 연결한다.

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

type AddValue<T extends any[], V> = T extends T
  ? T | [V, ...T]
  : never

리팩토링

다음과 같이 하나의 함수로 만들 수도 있다.

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

---

혹시 오류나 개선점이 있으면 댓글 남겨주세요!