46. Permutations

Задача

Дан массив различных чисел 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]]

Решение

Решение

/**
 * Временная сложность: O(n! × n)
 * - Генерируем n! перестановок (факториал от длины массива)
 * - Каждую перестановку копируем в result за O(n)
 * - На каждом уровне рекурсии перебираем до n элементов
 * 
 * Пространственная сложность: O(n)
 * - Глубина рекурсии: O(n) - максимум n вызовов в стеке
 * - Массив used: O(n)
 * - Массив current: O(n)
 * - Не считаем result (это выходные данные)
 */
function permute(nums) {
    const result = [];
    const current = [];
    const used = new Array(nums.length).fill(false);
 
    function backtrack() {
        if (current.length === nums.length) {
            result.push([...current]); // O(n) операция копирования
            return;
        }
 
        for (let i = 0; i < nums.length; i++) { // O(n) итераций
            if (used[i]) continue;
 
            current.push(nums[i]);
            used[i] = true;
            backtrack();
            current.pop();
            used[i] = false;
        }
    }
 
    backtrack();
    return result;
}

Решение 2 (Backtracking со swap (наиболее эффективное))

/**
 * Временная сложность: O(n! × n)
 * - Генерируем n! перестановок
 * - Каждую копируем за O(n)
 * 
 * Пространственная сложность: O(n)
 * - Только глубина рекурсии: O(n)
 * - НЕ используем дополнительные массивы (used, current)
 * - Модифицируем исходный массив in-place через swap
 * - Самое экономное по памяти решение!
 */
function permute(nums) {
    const result = [];
 
    function backtrack(start) {
        if (start === nums.length) {
            result.push([...nums]); // O(n) копирование
            return;
        }
 
        for (let i = start; i < nums.length; i++) {
            [nums[start], nums[i]] = [nums[i], nums[start]]; // O(1) swap
            backtrack(start + 1);
            [nums[start], nums[i]] = [nums[i], nums[start]]; // O(1) откат
        }
    }
 
    backtrack(0);
    return result;
}