Subsets, Combinations, Combination Sum.
Систематический перебор с возвратом: строим решение пошагово, откатываемся при достижении тупика. Основа для комбинаторных задач.
Backtracking — это улучшенный перебор: строим решение постепенно, отбрасывая частичные решения, которые не могут привести к полному.
Рекурсия — вызов функцией самой себя.
Итерация — однократное выполнение цикла.
Базовый случай — условие завершения рекурсии (чтобы избежать бесконечной рекурсии).
Стек вызовов — структура данных, хранящая активные вызовы функций.
Backtracking — систематический перебор с возвратом (откатом) при достижении тупика.
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)Условие:
Дан массив целых чисел nums с уникальными элементами. Верните все возможные подмножества (булеан). Решение не должно содержать дубликатов подмножеств.
Примеры:
Ввод: nums = [1,2,3]
Вывод: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Ввод: nums = [0]
Вывод: [[],[0]]
Ограничения:
💡 Подсказка: Добавляйте текущий путь в результат в НАЧАЛЕ каждой итерации backtrack. Это добавит все подмножества.
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Объяснение:
Сложность:
Условие:
Даны два целых числа 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]]
Ограничения:
💡 Подсказка: Базовый случай: когда длина пути равна 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Объяснение:
Сложность:
Условие:
Дан массив различных целых чисел 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]]
Ограничения:
💡 Подсказка: Передавайте
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, ...) — можно использовать тот же элемент сноваСложность:
Условие:
Дан массив кандидатов 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]]
Ограничения:
💡 Подсказка: Отсортируйте массив. Пропускайте дубликаты:
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 — каждый элемент используется один разСложность:
Условие:
Дан целочисленный массив nums, который может содержать дубликаты. Верните все возможные подмножества (булеан). Решение не должно содержать дубликатов подмножеств.
Примеры:
Ввод: nums = [1,2,2]
Вывод: [[],[1],[1,2],[1,2,2],[2],[2,2]]
Ввод: nums = [0]
Вывод: [[],[0]]
Ограничения:
💡 Подсказка: Отсортируйте массив. Пропускайте дубликаты:
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 важна: пропускаем только на том же уровне, но не между уровнямиСложность:
# Неправильно
path.append(i)
backtrack(i + 1, path)
# Забыли path.pop()!
# Правильно
path.append(i)
backtrack(i + 1, path)
path.pop()# Неправильно
result.append(path) # Ссылка на тот же список!
# Правильно
result.append(path[:]) # Копия# После сортировки
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]:
continue # Пропускаем дубликаты на этом уровне| Задача | Ключевая идея |
|---|---|
| Subsets | result.append в начале |
| Combinations | if len(path) == k |
| Combination Sum | backtrack(i, ...) — можно повторять |
| Combination Sum II | i > start и дубликаты |
| Subsets II | sort + skip duplicates |
Проблема: Забыли удалить элемент после рекурсивного вызова.
# ❌ Неправильно — забыли 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() после рекурсивного вызова.
Проблема: Передача ссылки на список вместо копии.
# ❌ Неправильно — передаём ссылку
result.append(path) # Все элементы result ссылаются на один path!
# После всех pop() все элементы result станут []
# ✅ Правильно — создаём копию
result.append(path[:]) # или list(path), или path.copy()Почему это неправильно: Все элементы result будут ссылаться на один и тот же список.
Как обнаружить: В результате все пути пустые или одинаковые.
Как исправить: Используйте path[:] для создания копии.
Проблема: Не пропускаем дубликаты в задачах с повторениями.
# ❌ Неправильно — нет проверки дубликатов
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
Проблема: Неправильное условие завершения рекурсии.
# ❌ Неправильно для Combinations — не то условие
if start == n: # Не то!
result.append(path[:])
return
# ✅ Правильно — проверяем длину path
if len(path) == k: # Нашли комбинацию размера k
result.append(path[:])
returnПочему это неправильно: Базовый случай должен проверять решение, а не индекс.
Как обнаружить: Пустой результат или неправильные комбинации.
Как исправить: Проверяйте условие решения (длина path, сумма, и т.д.)
Backtracking: Основы — базовый паттерн для генерации подмножеств и комбинаций.
Ключевые принципы:
path.pop() после рекурсивного вызоваpath[:] для копирования спискаi > starti (не i+1) для повторного использованияВопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.