Комбинации с суммой: бэктрекинг в Python

Зачем разбирать Combination Sum на Python?

Задача Combination Sum — это классика собеседований в FAANG и не только. Она проверяет ваше умение применять бэктрекинг (backtracking) для генерации всех комбинаций с повторениями. Если вы хотите уверенно решать задачи на суммы и подмножества, этот разбор для вас.

Условие задачи

Дан массив различных целых чисел candidates и целевое число target. Нужно вернуть все уникальные комбинации, где сумма выбранных чисел равна target. Одно и то же число можно использовать неограниченное количество раз.

Пример:

candidates = [2, 3, 6, 7]
target = 7

# Ожидаемый результат:
[
  [2, 2, 3],
  [7]
]

Почему бэктрекинг?

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

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

Решение на Python

Вот рабочий код с комментариями на русском:

from typing import List

def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
    ans = []  # Список для хранения всех комбинаций

    def backtrack(start: int, target: int, path: List[int]):
        """
        start — текущий индекс в candidates
        target — оставшаяся сумма
        path — текущая комбинация
        """
        if target == 0:
            # Нашли валидную комбинацию
            ans.append(path[:])
            return
        if target < 0:
            # Перебор, отсекаем ветвь
            return

        for i in range(start, len(candidates)):
            # Выбираем элемент candidates[i]
            path.append(candidates[i])
            # Остаёмся на том же i, так как можно использовать повторно
            backtrack(i, target - candidates[i], path)
            # Откатываем (backtrack)
            path.pop()

    backtrack(0, target, [])
    return ans

Как это работает:

• Мы рекурсивно перебираем элементы, начиная с индекса start.
• Если target стал 0 — сохраняем копию текущего пути.
• Если target стал отрицательным — прекращаем эту ветвь.
• После взятия элемента вызываем backtrack с тем же индексом i, чтобы разрешить повторное использование.

Разбор на примере

Пусть candidates = [2, 3, 6, 7], target = 7. Дерево рекурсии:

target=7
├── берём 2 → target=5
│   ├── берём 2 → target=3
│   │   ├── берём 2 → target=1 (отрицательный, отсекаем)
│   │   └── берём 3 → target=0 ✅ [2,2,3]
│   ├── берём 3 → target=2
│   │   └── берём 2 → target=0 ✅ [2,3,2] (но это дубликат, так как порядок не важен? На самом деле наш алгоритм не генерирует дубликаты, потому что мы не перебираем заново с начала)
│   └── ...
└── берём 7 → target=0 ✅ [7]

Обратите внимание: мы не перебираем элементы, которые уже были слева, поэтому комбинации не повторяются. В итоге получаем [[2,2,3], [7]].

Сложность алгоритма

• Время: O(2^T), где T — target. В худшем случае (например, candidates = [1]) дерево рекурсии имеет глубину T и ветвление 2.
• Память: O(T) — глубина рекурсии и хранение текущего пути.

Что делать прямо сейчас?

Откройте LeetCode, найдите задачу Combination Sum и решите её самостоятельно, используя наш шаблон. Потренируйтесь на похожих задачах: Combination Sum II (без повторного использования), Coin Change (количество способов), Subsets. Успехов!