// ============= Test Cases =============
import type { Equal, Expect } from "./test-utils";

type A1 = AllCombinations<"">;
type B1 = "";
type C1 = Expect<Equal<A1, B1>>;

type A2 = AllCombinations<"A">;
type B2 = "" | "A";
type C2 = Expect<Equal<A2, B2>>;

type A3 = AllCombinations<"AB">;
type B3 =
  | "" | "A" | "B"
  | "AB" | "BA"
;
type C3 = Expect<Equal<A3, B3>>;

type A4 = AllCombinations<"ABC">;
type B4 = 
  | ""
  | "A"
  | "B"
  | "C"
  | "AB" | "AC"
  | "BA" | "BC"
  | "CA" | "CB"
  | "ABC" | "ACB"
  | "BAC" | "BCA"
  | "CAB" | "CBA"
;
type C4 = Expect<Equal<A4, B4>>;

type A5 = AllCombinations<"ABCD">;
type B5 =
  | ""
  | "A"
  | "B"
  | "C"
  | "D"
  | "AB" | "AC" | "AD"
  | "BA" | "BC" | "BD"
  | "CA" | "CB" | "CD"
  | "DA" | "DB" | "DC"
  | "ABC" | "ABD" | "ACB" | "ACD" | "ADB" | "ADC"
  | "BAC" | "BAD" | "BCA" | "BCD" | "BDA" | "BDC"
  | "CAB" | "CAD" | "CBA" | "CBD" | "CDA" | "CDB"
  | "DAB" | "DAC" | "DBA" | "DBC" | "DCA" | "DCB"
  | "ABCD" | "ABDC" | "ACBD" | "ACDB" | "ADBC" | "ADCB"
  | "BACD" | "BADC" | "BCAD" | "BCDA" | "BDAC" | "BDCA"
  | "CABD" | "CADB" | "CBAD" | "CBDA" | "CDAB" | "CDBA"
  | "DABC" | "DACB" | "DBAC" | "DBCA" | "DCAB" | "DCBA"
;
type C5 = Expect<Equal<A5, B5>>;

// ============= Your Code Here =============
// previous challenge: 43
type Exclude<T, U> = T extends U ? never : T;

// previous challenge: 1042
type IsNever<T> = [T] extends [never] ? true : false;

// previous challenge: 531
type StringToUnion<T> =
  T extends `${infer Head}${infer Tail}`
  ? Head | StringToUnion<Tail>
  : never;

type AllCombinations<
  S,
  Acc extends string = StringToUnion<S>
> =
  IsNever<Acc> extends true
  ? ""
  : "" | {
    [Combo in Acc]:
      `${
        Combo
      }${
        AllCombinations<
          never,
          Exclude<Acc, Combo>
        >
      }`
  }[Acc];

// ============== Alternatives ==============
type StringToUnion<S extends string> =
  S extends `${infer Head}${infer Tail}`
  ? Head | StringToUnion<Tail>
  : S; // this variant doesn't return never
type Combination<A extends string, B extends string> =
  | A
  | B
  | `${A}${B}`
  | `${B}${A}`;
type UnionCombination<
  A extends string,
  B extends string = A
> =
  A extends B
  ? Combination<A, UnionCombination<Exclude<B, A>>>
  : never;
type AllCombinations<S extends string> =
  UnionCombination<StringToUnion<S>>

type AllCombinations<
  S extends string,
  Acc extends string = ''
> =
  S extends `${infer Head}${infer Tail}`
  ?
    | `${Head}${AllCombinations<`${Acc}${Tail}`>}`
    | AllCombinations<Tail, `${Acc}${Head}`>
  : '';