5. Permutations

«Порядок имеет значение только тогда, когда мы способны различить его последствия».
— Чарльз Хоар

В задачах 3. Subsets и 4. Subsets II порядок элементов не имел значения: подмножества {1, 2} и {2, 1} считались эквивалентными, а переход i + 1 гарантировал выбор только «вправо».

Задача Permutations (LeetCode 46) открывает принципиально другой комбинаторный класс:
Условие: Дан срез различных целых чисел nums. Требуется вернуть все возможные перестановки (всего $N!$ штук).

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

Архитектура: Дерево пространства состояний для nums = [1, 2, 3]

На каждом шаге мы выбираем любой еще не использованный элемент из исходного множества. Дерево решений для массива [1, 2, 3] содержит ровно $3! = 6$ листьев:

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Root["Корень: []"]:::entry

    %% Уровень 1
    Root -->|"выбор 1"| P1["[1]"]:::process
    Root -->|"выбор 2"| P2["[2]"]:::process
    Root -->|"выбор 3"| P3["[3]"]:::process

    %% Ветви от [1]
    P1 -->|"выбор 2"| P12["[1, 2]"]:::process
    P1 -->|"выбор 3"| P13["[1, 3]"]:::process
    P12 -->|"выбор 3"| L1["[1, 2, 3]"]:::success
    P13 -->|"выбор 2"| L2["[1, 3, 2]"]:::success

    %% Ветви от [2]
    P2 -->|"выбор 1"| P21["[2, 1]"]:::process
    P2 -->|"выбор 3"| P23["[2, 3]"]:::process
    P21 -->|"выбор 3"| L3["[2, 1, 3]"]:::success
    P23 -->|"выбор 1"| L4["[2, 3, 1]"]:::success

    %% Ветви от [3]
    P3 -->|"выбор 1"| P31["[3, 1]"]:::process
    P3 -->|"выбор 2"| P32["[3, 2]"]:::process
    P31 -->|"выбор 2"| L5["[3, 1, 2]"]:::success
    P32 -->|"выбор 1"| L6["[3, 2, 1]"]:::success
  

Идиоматичная реализация на Go

Существует два равноправных подхода: классический с трекингом флагов visited и компактный in-place swap. На собеседовании ожидается первый как наиболее расширяемый на задачи с дубликатами.

package main

// permute генерирует все N! перестановок уникального массива.
// Временная сложность: O(N * N!)
// Пространственная сложность: O(N) под стек и буфер path
func permute(nums []int) [][]int {
    n := len(nums)
    if n == 0 {
        return nil
    }

    var result [][]int
    path := make([]int, 0, n)
    visited := make([]bool, n) // Флаги занятости элементов

    var backtrack func()
    backtrack = func() {
        // Базовый случай: собрана полная перестановка длины n
        if len(path) == n {
            snapshot := make([]int, n)
            copy(snapshot, path)
            result = append(result, snapshot)
            return
        }

        // Перебираем ВСЕ элементы, пропуская уже использованные
        for i := 0; i < n; i++ {
            if visited[i] {
                continue
            }

            // Choose
            visited[i] = true
            path = append(path, nums[i])

            // Explore
            backtrack()

            // Unchoose (откат обоих инвариантов)
            path = path[:len(path)-1]
            visited[i] = false
        }
    }

    backtrack()
    return result
}

Взгляд под капот: Mechanical Sympathy

1. visited []bool против Битовой маски mask int

В решении выше visited выделяется в куче один раз (make([]bool, n)). Чтение visited[i] требует загрузки адреса из L1 Data Cache.
Для $N \le 64$ битовая маска целиком укладывается в регистр процессора:

// Проверка бита: (mask & (1 << i)) != 0
// Установка бита: mask | (1 << i)

• Инструкция x86-64 BT (Bit Test) или AND выполняется за 1 такт CPU в ALU.
• Не требуется выделять память под массив флагов.
• Откат маски происходит автоматически: значение передается в рекурсивную функцию по значению (на регистре RDX), поэтому при возврате из функции старое значение маски мгновенно восстанавливается без явных операций!

2. In-Place Swap: алгоритм с $O(1)$ вспомогательной памяти

Если интервьюер просит решение без дополнительного массива visited и среза path:

func permuteSwap(nums []int) [][]int {
    var result [][]int
    var backtrack func(start int)
    backtrack = func(start int) {
        if start == len(nums) {
            snapshot := make([]int, len(nums))
            copy(snapshot, nums)
            result = append(result, snapshot)
            return
        }
        for i := start; i < len(nums); i++ {
            nums[start], nums[i] = nums[i], nums[start] // Swap
            backtrack(start + 1)
            nums[start], nums[i] = nums[i], nums[start] // Un-swap
        }
    }
    backtrack(0)
    return result
}

Swap-подход элегантен, но имеет недостаток: порядок генерируемых перестановок не является лексикографическим, а адаптация под массивы с дубликатами требует дополнительной дедупликации.

Подводные камни и вопросы с собеседований

Резюме

Permutations демонстрирует управление порядком следования:

• Цикл перебирает всех кандидатов от $0$ до $n-1$.
• Флаги visited гарантируют, что каждый элемент входит в перестановку ровно один раз.
• Откат восстанавливает как срез path, так и булеву маску visited.

Что делать, если в исходном наборе чисел присутствуют дубликаты (например, [1, 1, 2])? Обычный visited сгенерирует одинаковые перестановки. Решение этой задачи мы разберем в следующей статье: 6. Permutations II.