Перестановки (backtracking)

1function permutations<T>(items: T[]): T[][] {
2  const result: T[][] = []
3 
4  function backtrack(current: T[], rest: T[]): void {
5    if (rest.length === 0) {
6      result.push([...current])
7      return
8    }
9    for (let i = 0; i < rest.length; i++) {
10      const next = rest[i]!
11      current.push(next)                 // выбираем
12      backtrack(current, rest.filter((_, j) => j !== i))
13      current.pop()                      // откатываем
14    }
15  }
16 
17  backtrack([], items)
18  return result
19}