Backtracking: Основы

Систематический перебор с возвратом: строим решение пошагово, откатываемся при достижении тупика. Основа для комбинаторных задач.

#1. Суть паттерна

Backtracking — это улучшенный перебор: строим решение постепенно, отбрасывая частичные решения, которые не могут привести к полному.

#1.1 Термины

Рекурсия — вызов функцией самой себя.

Итерация — однократное выполнение цикла.

Базовый случай — условие завершения рекурсии (чтобы избежать бесконечной рекурсии).

Стек вызовов — структура данных, хранящая активные вызовы функций.

Backtracking — систематический перебор с возвратом (откатом) при достижении тупика.

#Когда применять

✅ Комбинации — выбрать k элементов из n
✅ Перестановки — все порядки элементов
✅ Подмножества — все возможные наборы
✅ N-ферзей — размещение с ограничениями
✅ Сумма подмножества — комбинации с суммой

#Шаблон

def backtrack(start, path):
    # Базовый случай
    if is_solution(path):
        result.append(path[:])
        return

    # Перебор кандидатов
    for i in range(start, n):
        if is_valid(i):
            path.append(i)           # Выбрать
            backtrack(i + 1, path)   # Исследовать
            path.pop()               # Откат (backtrack)

#2. Разбор задач

#Задача 1: Subsets (LeetCode 78) 🟦 Medium

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

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

Примеры:

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

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

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

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

💡 Подсказка: Добавляйте текущий путь в результат в НАЧАЛЕ каждой итерации backtrack. Это добавит все подмножества.

#Визуализация: Backtracking дерево для Subsets

nums = [1, 2, 3]

Дерево решений:
                    []
                   /  \
                 [1]   []
                /  \    \
           [1,2]  [1]   [2]
           /  \    \     /  \
      [1,2,3] [1,2] [1,3] [2,3]
                \    \   /    /
                [1]  [1][2]  [3]

Порядок обхода (DFS):
1. [] ← добавляем
2. [1] ← добавляем
3. [1,2] ← добавляем
4. [1,2,3] ← добавляем, backtrack
5. [1,2] ← backtrack
6. [1] ← добавляем [1,3], backtrack
7. [1] ← backtrack
8. [] ← добавляем [2], добавляем [2,3], backtrack
9. [2] ← backtrack
10. [] ← добавляем [3], backtrack

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

Решение:

def subsets(nums):
    result = []

    def backtrack(start, path):
        result.append(path[:])  # Добавляем текущее подмножество

        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()  # Backtrack

    backtrack(0, [])
    return result

Объяснение:

В начале каждой итерации добавляем текущий путь в результат
Это добавляет все подмножества: пустое, все размера 1, 2, и т.д.
Базового случая нет — цикл просто не выполнится, когда start >= len(nums)

Сложность:

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

#Задача 2: Combinations (LeetCode 77) 🟦 Medium

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

Условие: Даны два целых числа n и k. Верните все возможные комбинации из k чисел в диапазоне от 1 до n.

Примеры:

Ввод: n = 4, k = 2
Вывод: [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Ввод: n = 1, k = 1
Вывод: [[1]]

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

1 <= n <= 20
1 <= k <= n

💡 Подсказка: Базовый случай: когда длина пути равна k. Перебирайте числа от start до n.

Решение:

def combine(n, k):
    result = []

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

        for i in range(start, n + 1):
            path.append(i)
            backtrack(i + 1, path)
            path.pop()

    backtrack(1, [])
    return result

Объяснение:

Базовый случай: len(path) == k — набрали нужное количество элементов
Перебираем числа от start до n (включительно)
i + 1 передаётся, чтобы не было повторений и порядок не важен

Сложность:

Время: O(C(n,k) × k) — количество комбинаций × копирование
Память: O(k) — глубина рекурсии

#Задача 3: Combination Sum (LeetCode 39) 🟦 Medium

Ссылка: https://leetcode.com/problems/combination-sum/

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

Одно и то же число может быть выбрано неограниченное количество раз.

Примеры:

Ввод: candidates = [2,3,6,7], target = 7
Вывод: [[2,2,3],[7]]

Ввод: candidates = [2,3,5], target = 8
Вывод: [[2,2,2,2],[2,3,3],[3,5]]

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

2 <= candidates.length <= 30
2 <= candidates[i] <= 40
1 <= target <= 40

💡 Подсказка: Передавайте i (не i+1) в рекурсивный вызов, чтобы разрешить повторное использование элемента.

Решение:

def combinationSum(candidates, target):
    result = []

    def backtrack(start, path, total):
        if total == target:
            result.append(path[:])
            return
        if total > target:
            return

        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, path, total + candidates[i])  # i, не i+1
            path.pop()

    backtrack(0, [], 0)
    return result

Объяснение:

backtrack(i, ...) — можно использовать тот же элемент снова
Два базовых случая: total == target (успех) и total > target (отсечение)
Сумму передаём как параметр для эффективности

Сложность:

Время: O(T/min(candidates) × n) — зависит от target
Память: O(T/min(candidates)) — глубина рекурсии

#Задача 4: Combination Sum II (LeetCode 40) 🟦 Medium

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

Условие: Дан массив кандидатов candidates и целевое значение target. Верните все уникальные комбинации, где числа суммируются в target.

Каждое число может быть использовано только один раз. Решение не должно содержать дубликатов комбинаций.

Примеры:

Ввод: candidates = [10,1,2,7,6,1,5], target = 8
Вывод: [[1,1,6],[1,2,5],[1,7],[2,6]]

Ввод: candidates = [2,5,2,1,2], target = 5
Вывод: [[1,2,2],[5]]

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

1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30

💡 Подсказка: Отсортируйте массив. Пропускайте дубликаты: if i > start and candidates[i] == candidates[i-1].

Решение:

def combinationSum2(candidates, target):
    candidates.sort()
    result = []

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

        for i in range(start, len(candidates)):
            # Пропускаем дубликаты на этом уровне
            if i > start and candidates[i] == candidates[i-1]:
                continue

            if total + candidates[i] > target:
                break  # Отсечение

            path.append(candidates[i])
            backtrack(i + 1, path, total + candidates[i])
            path.pop()

    backtrack(0, [], 0)
    return result

Объяснение:

Сортировка группирует дубликаты
i > start and candidates[i] == candidates[i-1] — пропускаем дубликаты внутри одного уровня
i + 1 — каждый элемент используется один раз
Отсечение: если сумма превышает target, дальнейшие элементы тоже превысят

Сложность:

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

#Задача 5: Subsets II (LeetCode 90) 🟦 Medium

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

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

Примеры:

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

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

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

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

💡 Подсказка: Отсортируйте массив. Пропускайте дубликаты: if i > start and nums[i] == nums[i-1].

Решение:

def subsetsWithDup(nums):
    nums.sort()
    result = []

    def backtrack(start, path):
        result.append(path[:])

        for i in range(start, len(nums)):
            # Пропускаем дубликаты на этом уровне
            if i > start and nums[i] == nums[i-1]:
                continue

            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()

    backtrack(0, [])
    return result

Объяснение:

Сортировка группирует дубликаты
i > start and nums[i] == nums[i-1] — пропускаем дубликаты внутри одного уровня рекурсии
Проверка i > start важна: пропускаем только на том же уровне, но не между уровнями

Сложность:

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

#3. Типичные ошибки

#❌ Ошибка 1: Забыли backtrack

# Неправильно
path.append(i)
backtrack(i + 1, path)
# Забыли path.pop()!

# Правильно
path.append(i)
backtrack(i + 1, path)
path.pop()

#❌ Ошибка 2: Неправильная копия пути

# Неправильно
result.append(path)  # Ссылка на тот же список!

# Правильно
result.append(path[:])  # Копия

#❌ Ошибка 3: Пропуск дубликатов

# После сортировки
for i in range(start, len(nums)):
    if i > start and nums[i] == nums[i-1]:
        continue  # Пропускаем дубликаты на этом уровне

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

Задача	Ключевая идея
Subsets	result.append в начале
Combinations	if len(path) == k
Combination Sum	backtrack(i, ...) — можно повторять
Combination Sum II	i > start и дубликаты
Subsets II	sort + skip duplicates

#5. ⚠️ Common Mistakes

#❌ Ошибка 1: Забыли backtrack (path.pop)

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

# ❌ Неправильно — забыли path.pop()
def backtrack(start, path):
    if is_solution(path):
        result.append(path[:])
        return

    for i in range(start, n):
        path.append(i)
        backtrack(i + 1, path)
        # path.pop() забыли! → path остаётся изменённым

# ✅ Правильно — делаем backtrack
def backtrack(start, path):
    if is_solution(path):
        result.append(path[:])
        return

    for i in range(start, n):
        path.append(i)
        backtrack(i + 1, path)
        path.pop()  # Откатываем!

Почему это неправильно: path остаётся изменённым, что влияет на следующие итерации.

Как обнаружить: Неправильные результаты, лишние элементы в ответе.

Как исправить: Всегда делайте path.pop() после рекурсивного вызова.

#❌ Ошибка 2: Неправильная копия пути

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

# ❌ Неправильно — передаём ссылку
result.append(path)  # Все элементы result ссылаются на один path!
# После всех pop() все элементы result станут []

# ✅ Правильно — создаём копию
result.append(path[:])  # или list(path), или path.copy()

Почему это неправильно: Все элементы result будут ссылаться на один и тот же список.

Как обнаружить: В результате все пути пустые или одинаковые.

Как исправить: Используйте path[:] для создания копии.

#❌ Ошибка 3: Пропуск дубликатов

Проблема: Не пропускаем дубликаты в задачах с повторениями.

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

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

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

Как обнаружить: Дубликаты в результате.

Как исправить: Сортируйте массив и пропускайте дубликаты: if i > start and nums[i] == nums[i-1]: continue

#❌ Ошибка 4: Неправильный базовый случай

Проблема: Неправильное условие завершения рекурсии.

# ❌ Неправильно для Combinations — не то условие
if start == n:  # Не то!
    result.append(path[:])
    return

# ✅ Правильно — проверяем длину path
if len(path) == k:  # Нашли комбинацию размера k
    result.append(path[:])
    return

Почему это неправильно: Базовый случай должен проверять решение, а не индекс.

Как обнаружить: Пустой результат или неправильные комбинации.

Как исправить: Проверяйте условие решения (длина path, сумма, и т.д.)

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

Backtracking: Основы — базовый паттерн для генерации подмножеств и комбинаций.

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

Всегда делайте path.pop() после рекурсивного вызова
Используйте path[:] для копирования списка
Для дубликатов: сортировка + проверка i > start
Combination Sum: передавайте i (не i+1) для повторного использования

nums = [1, 2, 3] Дерево решений: [] / \ [1] [] / \ \ [1,2] [1] [2] / \ \ / \ [1,2,3] [1,2] [1,3] [2,3] \ \ / / [1] [1][2] [3] Порядок обхода (DFS): 1. [] ← добавляем 2. [1] ← добавляем 3. [1,2] ← добавляем 4. [1,2,3] ← добавляем, backtrack 5. [1,2] ← backtrack 6. [1] ← добавляем [1,3], backtrack 7. [1] ← backtrack 8. [] ← добавляем [2], добавляем [2,3], backtrack 9. [2] ← backtrack 10. [] ← добавляем [3], backtrack Результат: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Задача

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

Subsets

result.append в начале

Combinations

if len(path) == k

Combination Sum

backtrack(i, ...) — можно повторять

Combination Sum II

i > start и дубликаты

Subsets II

sort + skip duplicates