타입 챌린지 4260 - AllCombinations

문제 링크

문제

S에서 가져온 문자를 최대 1번 사용하는 문자열 조합을 리턴하는 타입 AllCombinations<S>를 구현하라

Implement type AllCombinations<S> that return all combinations of strings which use characters from S at most once.

내 풀이

type StringToTuple<S extends string,Result extends string[]=[]>=
  S extends `${infer First}${infer Last}`?
    StringToTuple<Last,[...Result,First]>
    :Result

type StringUnion<S extends string,Result extends string=StringToTuple<S>[number]>=[Result] extends [never]?'':Result;

type AllCombinations<S extends string,Used extends string = never,Unused extends string=StringUnion<S>,Tmp extends string=Unused> = 
  Unused extends Tmp?
    Unused|AllCombinations<'',Used|Unused,Exclude<Tmp,Unused>>|`${Unused}${AllCombinations<'',Used|Unused,Exclude<Tmp,Unused>>}`|''
  :''

string을 union으로 변경해 조합을 구현했다.

조금 힘들었던 부분은 Unused에 never가 들어가게 되면 분배법칙이 시행되지 않아 never가 뜬다는 점이였는데,

그것을 명시적으로 ''를 반환하게 함으로써 해결했다

다른 사람의 풀이

type String2Union<S extends string> =
  S extends `${infer C}${infer REST}`
  ? C | String2Union<REST>
  : never;

type AllCombinations<
  STR extends string,
  S extends string = String2Union<STR>,
> = [S] extends [never]
  ? ''
  : '' | {[K in S]: `${K}${AllCombinations<never, Exclude<S, K>>}`}[S];
  

string을 유니온으로 바꾸는 것 까지는 동일했으나 mapped 타입을 이용해 조합을 구현해냈다

참고자료

https://github.com/type-challenges/type-challenges/issues/5339