Backtracking: Permutations

Генерация всех перестановок и упорядоченных комбинаций. Используем backtracking с отслеживанием использованных элементов.

#1. Permutations (LeetCode 46) 🟦 Medium

Ссылка: https://leetcode.com/problems/permutations/

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

Примеры:

Ввод: nums = [1,2,3]
Вывод: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Ввод: nums = [0,1]
Вывод: [[0,1],[1,0]]

Ввод: nums = [1]
Вывод: [[1]]

Ограничения:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
Все элементы уникальны

💡 Подсказка: Проверяйте if num not in path, чтобы не использовать элемент дважды.

#Визуализация: Backtracking для Permutations

nums = [1, 2, 3]

Дерево перестановок:
                        []
                      /  |  \
                    [1] [2] [3]
                   / \  / \  / \
               [1,2][1,3][2,1][2,3][3,1][3,2]
                 |    |    |    |    |    |
              [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

Порядок обхода:
1. [] → [1] → [1,2] → [1,2,3] ← добавляем
2. backtrack → [1,3] → [1,3,2] ← добавляем
3. backtrack → [] → [2] → [2,1] → [2,1,3] ← добавляем
4. backtrack → [2,3] → [2,3,1] ← добавляем
5. backtrack → [] → [3] → [3,1] → [3,1,2] ← добавляем
6. backtrack → [3,2] → [3,2,1] ← добавляем

Результат: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Решение:

def permute(nums):
    result = []

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for num in nums:
            if num not in path:  # Элемент ещё не использован
                path.append(num)
                backtrack(path)
                path.pop()

    backtrack([])
    return result

Объяснение:

Проверяем if num not in path для отслеживания использованных элементов
Базовый случай: длина пути равна длине nums
Можно также использовать set visited или менять элементы местами

Сложность:

Время: O(n! × n) — n! перестановок
Память: O(n) — глубина рекурсии

#2. Permutations II (LeetCode 47) 🟦 Medium

Ссылка: https://leetcode.com/problems/permutations-ii/

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

Примеры:

Ввод: nums = [1,1,2]
Вывод: [[1,1,2], [1,2,1], [2,1,1]]

Ввод: nums = [1,2,3]
Вывод: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Ограничения:

1 <= nums.length <= 8
-10 <= nums[i] <= 10

💡 Подсказка: Используйте boolean массив used для отслеживания. Пропускайте дубликаты: if i > 0 and nums[i] == nums[i-1] and not used[i-1].

Решение:

def permuteUnique(nums):
    nums.sort()
    result = []
    used = [False] * len(nums)

    def backtrack(path):
        if len(path) == len(nums):
            result.append(path[:])
            return

        for i in range(len(nums)):
            if used[i]:
                continue
            # Пропускаем дубликаты: если предыдущий такой же элемент не использован
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue

            used[i] = True
            path.append(nums[i])
            backtrack(path)
            path.pop()
            used[i] = False

    backtrack([])
    return result

Объяснение:

Сортировка группирует дубликаты
used[i] отслеживает, используется ли элемент в текущем пути
i > 0 and nums[i] == nums[i-1] and not used[i-1] — пропускаем дубликаты
Условие not used[i-1] важно: пропускаем только если предыдущий дубликат не в текущем пути

Сложность:

Время: O(n! × n)
Память: O(n)

#3. Letter Combinations of Phone Number (LeetCode 17) 🟦 Medium

Ссылка: https://leetcode.com/problems/letter-combinations-of-a-phone-number/

Условие: Дана строка digits, содержащая цифры от 2 до 9. Верните все возможные комбинации букв, которые могут быть представлены этими цифрами на телефонной клавиатуре.

Примеры:

Ввод: digits = "23"
Вывод: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Ввод: digits = ""
Вывод: []

Ввод: digits = "2"
Вывод: ["a","b","c"]

Ограничения:

0 <= digits.length <= 4
digits[i] — цифра от '2' до '9'

💡 Подсказка: Используйте словарь для маппинга цифр в буквы. Отдельно обработайте пустую строку.

Решение:

def letterCombinations(digits):
    if not digits:
        return []

    phone = {
        '2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
        '6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
    }

    result = []

    def backtrack(index, path):
        if index == len(digits):
            result.append(path)
            return

        for letter in phone[digits[index]]:
            backtrack(index + 1, path + letter)

    backtrack(0, '')
    return result

Объяснение:

Отдельная проверка: if not digits → return []
Базовый случай: index == len(digits)
path + letter создаёт новую строку (не нужно backtrack)

Сложность:

Время: O(4^n × n) — максимум 4 буквы на цифру
Память: O(n) — глубина рекурсии

#4. Generate Parentheses (LeetCode 22) 🟦 Medium

Ссылка: https://leetcode.com/problems/generate-parentheses/

Условие: Дано число n. Сгенерируйте все комбинации корректных скобочных последовательностей из n пар скобок.

Примеры:

Ввод: n = 3
Вывод: ["((()))","(()())","(())()","()(())","()()()"]

Ввод: n = 1
Вывод: ["()"]

Ограничения:

1 <= n <= 8

💡 Подсказка: Два условия: '(' можно добавить, если open_count < n; ')' можно добавить, если close_count < open_count.

Решение:

def generateParenthesis(n):
    result = []

    def backtrack(path, open_count, close_count):
        if len(path) == 2 * n:
            result.append(path)
            return

        # Можно добавить открывающую скобку
        if open_count < n:
            backtrack(path + '(', open_count + 1, close_count)

        # Можно добавить закрывающую скобку
        if close_count < open_count:
            backtrack(path + ')', open_count, close_count + 1)

    backtrack('', 0, 0)
    return result

Объяснение:

open_count < n — можно добавить '('
close_count < open_count — можно добавить ')'
Базовый случай: длина пути равна 2n

Сложность:

Время: O(4^n / √n) — каталанское число
Память: O(n)

#5. Palindrome Partitioning (LeetCode 131) 🟦 Medium

Ссылка: https://leetcode.com/problems/palindrome-partitioning/

Условие: Дана строка s. Разбейте s на подстроки так, чтобы каждая подстрока была палиндромом. Верните все возможные разбиения.

Примеры:

Ввод: s = "aab"
Вывод: [["a","a","b"],["aa","b"]]

Ввод: s = "a"
Вывод: [["a"]]

Ограничения:

1 <= s.length <= 16
s состоит из строчных английских букв

💡 Подсказка: Проверяйте is_palindrome(substring) перед добавлением в путь.

Решение:

def partition(s):
    result = []

    def is_palindrome(sub):
        return sub == sub[::-1]

    def backtrack(start, path):
        if start == len(s):
            result.append(path[:])
            return

        for i in range(start, len(s)):
            substring = s[start:i+1]
            if is_palindrome(substring):
                path.append(substring)
                backtrack(i + 1, path)
                path.pop()

    backtrack(0, [])
    return result

Объяснение:

Проверяем is_palindrome перед добавлением подстроки
Базовый случай: start == len(s) — достигли конца строки
s[start:i+1] — подстрока от start до i включительно

Сложность:

Время: O(n × 2^n)
Память: O(n)

#6. Restore IP Addresses (LeetCode 93) 🟦 Medium

Ссылка: https://leetcode.com/problems/restore-ip-addresses/

Условие: Дана строка s, содержащая только цифры. Верните все возможные валидные IP-адреса, которые можно получить из строки.

Валидный IP-адрес состоит из 4 чисел от 0 до 255, разделённых точками.

Примеры:

Ввод: s = "25525511135"
Вывод: ["255.255.11.135","255.255.111.35"]

Ввод: s = "0000"
Вывод: ["0.0.0.0"]

Ввод: s = "101023"
Вывод: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Ограничения:

1 <= s.length <= 20
s состоит из цифр

💡 Подсказка: Валидный сегмент: длина 1 ИЛИ (не начинается с '0' и значение ≤ 255).

Решение:

def restoreIpAddresses(s):
    if len(s) < 4 or len(s) > 12:
        return []

    result = []

    def is_valid(segment):
        # '0' допустим, но '01', '001' — нет
        return (len(segment) == 1 or
                (segment[0] != '0' and int(segment) <= 255))

    def backtrack(start, path):
        if len(path) == 4:
            if start == len(s):
                result.append('.'.join(path))
            return

        for length in range(1, 4):
            if start + length > len(s):
                break

            segment = s[start:start+length]
            if is_valid(segment):
                path.append(segment)
                backtrack(start + length, path)
                path.pop()

    backtrack(0, [])
    return result

Объяснение:

is_valid: длина == 1 ИЛИ (первый символ не '0' И значение ≤ 255)
Базовый случай: 4 сегмента и использована вся строка
Длина сегмента: 1, 2 или 3 символа

Сложность:

Время: O(3^4) = O(1) — максимум 4 сегмента по 3 цифры
Память: O(1)

#7. Шпаргалка

Задача	Ключевая идея
Permutations	if num not in path
Permutations II	used array + skip duplicates
Letter Combinations	phone dictionary mapping
Generate Parentheses	open < n, close < open
Palindrome Partitioning	is_palindrome check
Restore IP	is_valid segment (0-255)

#8. ⚠️ Common Mistakes

#❌ Ошибка 1: Неправильное отслеживание использованных элементов

Проблема: Используем элемент дважды в перестановках.

# ❌ Неправильно — нет проверки
for num in nums:
    path.append(num)
    backtrack(path)
    path.pop()

# ✅ Правильно — проверяем использованные
for num in nums:
    if num not in path:  # Элемент ещё не использован
        path.append(num)
        backtrack(path)
        path.pop()

Почему это неправильно: Один и тот элемент будет использоваться многократно.

Как исправить: Проверяйте if num not in path или используйте boolean массив used.

#❌ Ошибка 2: Дубликаты в Permutations II

Проблема: Генерируем одинаковые перестановки.

# ❌ Неправильно — нет проверки дубликатов
nums = [1, 1, 2]
# Результат: [[1,1,2], [1,1,2], [1,2,1], [1,2,1], [2,1,1], [2,1,1]]

# ✅ Правильно — сортировка + проверка
nums.sort()
for i in range(len(nums)):
    if used[i]:
        continue
    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
        continue  # Пропускаем дубликат
    used[i] = True
    path.append(nums[i])
    backtrack(path)
    path.pop()
    used[i] = False

Почему это неправильно: Одинаковые элементы генерируют одинаковые перестановки.

Как исправить: Сортировка + проверка i > 0 and nums[i] == nums[i-1] and not used[i-1].

#9. Заключение

Backtracking: Permutations — генерация всех упорядоченных комбинаций.

Ключевые принципы:

Используйте if num not in path или used array для отслеживания
Для дубликатов: сортировка + i > 0 and nums[i] == nums[i-1] and not used[i-1]
Базовый случай: len(path) == len(nums) для перестановок

nums = [1, 2, 3] Дерево перестановок: [] / | \ [1] [2] [3] / \ / \ / \ [1,2][1,3][2,1][2,3][3,1][3,2] | | | | | | [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1] Порядок обхода: 1. [] → [1] → [1,2] → [1,2,3] ← добавляем 2. backtrack → [1,3] → [1,3,2] ← добавляем 3. backtrack → [] → [2] → [2,1] → [2,1,3] ← добавляем 4. backtrack → [2,3] → [2,3,1] ← добавляем 5. backtrack → [] → [3] → [3,1] → [3,1,2] ← добавляем 6. backtrack → [3,2] → [3,2,1] ← добавляем Результат: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Ввод: s = "25525511135" Вывод: ["255.255.11.135","255.255.111.35"] Ввод: s = "0000" Вывод: ["0.0.0.0"] Ввод: s = "101023" Вывод: ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

Задача

Ключевая идея

Permutations

if num not in path

Permutations II

used array + skip duplicates

Letter Combinations

phone dictionary mapping

Generate Parentheses

open < n, close < open

Palindrome Partitioning

is_palindrome check

Restore IP

is_valid segment (0-255)

Backtracking: Перестановки