Backtracking: Combination Sum

Задачи на сумму подмножества с backtracking. Разрешаем или запрещаем повторное использование элементов.

#1. 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)) — глубина рекурсии

#2. 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)

#3. 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)

#4. Palindrome Partitioning II (LeetCode 132) 🔴 Hard

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

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

Верните минимальное количество разрезов, необходимых для этого.

Примеры:

Ввод: s = "aab"
Вывод: 1
Объяснение: ["aa", "b"] — один разрез между "aa" и "b"

Ввод: s = "a"
Вывод: 0

Ввод: s = "ab"
Вывод: 1

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

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

💡 Подсказка: DP + palindrome check. dp[i] = минимальное количество разрезов для s[:i].

Решение:

def minCut(s):
    n = len(s)
    
    # Предварительно вычисляем палиндромы
    is_palindrome = [[False] * n for _ in range(n)]
    
    for i in range(n):
        is_palindrome[i][i] = True
    
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                if length == 2:
                    is_palindrome[i][j] = True
                else:
                    is_palindrome[i][j] = is_palindrome[i+1][j-1]
    
    # DP для минимального количества разрезов
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = i - 1  # Максимальное количество разрезов
    
    for i in range(1, n + 1):
        for j in range(i):
            if is_palindrome[j][i-1]:
                if j == 0:
                    dp[i] = 0
                else:
                    dp[i] = min(dp[i], dp[j] + 1)
    
    return dp[n]

Объяснение:

is_palindrome[i][j] = True, если s[i:j+1] — палиндром
dp[i] = минимальное количество разрезов для s[:i]
Если s[j:i] — палиндром, то dp[i] = min(dp[i], dp[j] + 1)

Сложность:

Время: O(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)

#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. Шпаргалка

Задача	Ключевая идея
Combination Sum	backtrack(i, ...) — можно повторять
Combination Sum II	i > start и дубликаты, i+1 — один раз
Palindrome Partitioning	is_palindrome check
Palindrome Partitioning II	DP + palindrome table
Subsets II	sort + skip duplicates
Restore IP	is_valid segment (0-255, no leading zero)

#8. ⚠️ Common Mistakes

#❌ Ошибка 1: Повторное использование в Combination Sum II

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

# ❌ Неправильно — передаём i
backtrack(i, path, total)  # Можно использовать снова!

# ✅ Правильно — передаём i+1
backtrack(i + 1, path, total)  # Каждый элемент один раз

Почему это неправильно: Combination Sum II требует использовать каждый элемент только один раз.

Как исправить: Передавайте i + 1 в рекурсивный вызов.

#❌ Ошибка 2: Пропуск дубликатов не на том уровне

Проблема: Неправильная проверка дубликатов.

# ❌ Неправильно — пропускаем всегда
if i > 0 and nums[i] == nums[i-1]:
    continue

# ✅ Правильно — пропускаем только на том же уровне
if i > start and nums[i] == nums[i-1]:
    continue

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

Как исправить: Используйте i > start для проверки на одном уровне.

#❌ Ошибка 3: Неправильная проверка IP сегмента

Проблема: Неправильная валидация сегмента IP.

# ❌ Неправильно — допускаем '01', '001'
if int(segment) <= 255:
    return True

# ✅ Правильно — проверяем ведущий ноль
return (len(segment) == 1 or
        (segment[0] != '0' and int(segment) <= 255))

Почему это неправильно: '01' и '001' невалидны в IP-адресе.

Как исправить: Проверяйте, что сегмент не начинается с '0', если длина > 1.

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

Backtracking: Combination Sum — задачи на сумму подмножества с различными ограничениями.

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

Combination Sum: backtrack(i, ...) — можно повторять
Combination Sum II: backtrack(i+1, ...) + skip duplicates
Palindrome Partitioning: is_palindrome check перед добавлением
Subsets II: sort + i > start and nums[i] == nums[i-1]
Restore IP: валидация сегмента (0-255, no leading zero)

Ввод: 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"]

Задача

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

Combination Sum

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

Combination Sum II

i > start и дубликаты, i+1 — один раз

Palindrome Partitioning

is_palindrome check

Palindrome Partitioning II

DP + palindrome table

Subsets II

sort + skip duplicates

Restore IP

is_valid segment (0-255, no leading zero)

Backtracking: Сумма