Combination Sum, Palindrome Partitioning, Restore IP.
Задачи на сумму подмножества с backtracking. Разрешаем или запрещаем повторное использование элементов.
Условие:
Дан массив различных целых чисел 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 — каждый элемент используется один разСложность:
Условие:
Дана строка s. Разбейте s на подстроки так, чтобы каждая подстрока была палиндромом. Верните все возможные разбиения.
Примеры:
Ввод: s = "aab"
Вывод: [["a","a","b"],["aa","b"]]
Ввод: s = "a"
Вывод: [["a"]]
Ограничения:
💡 Подсказка: Проверяйте
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Объяснение:
Сложность:
Условие:
Дана строка s. Разбейте s на подстроки так, чтобы каждая подстрока была палиндромом.
Верните минимальное количество разрезов, необходимых для этого.
Примеры:
Ввод: s = "aab"
Вывод: 1
Объяснение: ["aa", "b"] — один разрез между "aa" и "b"
Ввод: s = "a"
Вывод: 0
Ввод: s = "ab"
Вывод: 1
Ограничения:
💡 Подсказка: 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]Объяснение:
Сложность:
Условие:
Дан целочисленный массив 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 важна: пропускаем только на том же уровне, но не между уровнямиСложность:
Условие:
Дана строка 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 ИЛИ (не начинается с '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Объяснение:
Сложность:
| Задача | Ключевая идея |
|---|---|
| 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) |
Проблема: Используем элемент многократно в задаче, где нельзя.
# ❌ Неправильно — передаём i
backtrack(i, path, total) # Можно использовать снова!
# ✅ Правильно — передаём i+1
backtrack(i + 1, path, total) # Каждый элемент один разПочему это неправильно: Combination Sum II требует использовать каждый элемент только один раз.
Как исправить: Передавайте i + 1 в рекурсивный вызов.
Проблема: Неправильная проверка дубликатов.
# ❌ Неправильно — пропускаем всегда
if i > 0 and nums[i] == nums[i-1]:
continue
# ✅ Правильно — пропускаем только на том же уровне
if i > start and nums[i] == nums[i-1]:
continueПочему это неправильно: Проверка i > 0 пропускает дубликаты между уровнями, а не только на одном уровне.
Как исправить: Используйте i > start для проверки на одном уровне.
Проблема: Неправильная валидация сегмента 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.
Backtracking: Combination Sum — задачи на сумму подмножества с различными ограничениями.
Ключевые принципы:
backtrack(i, ...) — можно повторятьbacktrack(i+1, ...) + skip duplicatesi > start and nums[i] == nums[i-1]Вопросы ещё не добавлены
Вопросы для этой подтемы ещё не добавлены.