Задача с собеседования в eBay

Дан массив nums, состоящий из различных целых чисел. Верните все возможные перестановки этого массива. Вы можете вернуть ответ в любом порядке.

Пример 1:
Input: nums = [1,2,3]
Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Пример 2:
Input: nums = [0,1]
Output: [[0,1],[1,0]]

Пример 3:
Input: nums = [1]
Output: [[1]]

Ограничения:
1 <= nums.length <= 6
-10 <= nums[i] <= 10
Все числа в nums уникальны.

НАШ ЧАТ АЛГОРИТМИСТОВ

Решение
Так как необходимо вернуть все возможные перестановки элементов массива, используем backtracking - алгоритм поиска с возвратом.
Суть алгоритма: на каждом шаге добавляем элемент и строим полную правильную перестановку, после её сохранения последовательно возвращаемся по стеку вызовов до последней точки выбора и исследуем другие ветки из этой точки.

Создаём два списка:
res - для хранения найденных корректных перестановок;
permutation - временный список для "собирания" текущей перестановки.
Чтобы оптимизировать отслеживание уже использованных эл-тов, создаём множество used (проверка наличия эл-та за O(1) вместо O(n) при поиске по списку).

Запускаем рекурсивную функцию backtrack():
Базовый случай: если длина текущей перестановки достигла n (длина массива nums), значит: мы использовали все эл-ты -> перестановка готова -> сохраняем копию текущей перестановки в res (копия нужна, чтобы последующие изменения не затронули уже сохранённый ответ) и завершаем текущий вызов рекурсии, откатываясь назад.

Рекурсивное ветвление: перебираем все возможные эл-ты, которые можно добавить следующими.
Для каждого допустимого выбора (эл-та, которого ещё нет в текущей перестановке):
- добавляем значение в used ("помечаем" эл-т как использованный) и permutation (добавляет эл-т в текущую перестановку);
- вызываем рекурсию для выбора следующего значения;
- удаляем последнее добавленное значение из permutation (для возврата к развилке и исследованию другой ветки перестановки) и used (для возможности использования эл-та в других ветках).

Функция завершается, когда полностью исследовано дерево возможных перестановок.


Для этой задачи существует альтернативное решение через перестановки элементов в исходном массиве (in-place swapping). Делитесь им в комментариях!

Сложность
O(n*n!) - по времени (так как существует n! перестановок для массива размера n, каждая из них копируется в список за O(n))
O(n) - по памяти (стек рекурсии глубиной n, множество used размера n и список permutation размера n)

Код
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
res, permutation = [], []
used = set()

def backtrack():
if len(permutation) == n:
res.append(permutation[:])
return

for i in nums:
if i not in used:
used.add(i)
permutation.append(i)

backtrack()
permutation.pop()
used.remove(i)

backtrack()
return res

@algoses