Сложность: medium
Дан массив уникальных целых чисел candidates и целевое целое число target. Верните список всех уникальных комбинаций из candidates, где выбранные числа в сумме дают target. Комбинации можно возвращать в любом порядке.
Одно и то же число может быть выбрано из массива candidates неограниченное количество раз. Две комбинации считаются уникальными, если частота хотя бы одного из выбранных чисел отличается.
Тестовые случаи сгенерированы таким образом, что количество уникальных комбинаций, дающих в сумме target, меньше 150 комбинаций для данного ввода.
Пример:
Input: candidates = [2,3,5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
👨💻 Алгоритм:
1️⃣Как видно, вышеописанный алгоритм обратного отслеживания разворачивается как обход дерева в глубину (DFS - Depth-First Search), который часто реализуется с помощью рекурсии.
Здесь мы определяем рекурсивную функцию backtrack(remain, comb, start) (на Python), которая заполняет комбинации, начиная с текущей комбинации (comb), оставшейся суммы для выполнения (remain) и текущего курсора (start) в списке кандидатов.
Следует отметить, что сигнатура рекурсивной функции немного отличается в Java, но идея остается той же.
2️⃣Для первого базового случая рекурсивной функции, если remain == 0, то есть мы достигаем желаемой целевой суммы, поэтому мы можем добавить текущую комбинацию в итоговый список.
Как другой базовый случай, если remain < 0, то есть мы превышаем целевое значение, мы прекращаем исследование на этом этапе.
3️⃣Помимо вышеупомянутых двух базовых случаев, мы затем продолжаем исследовать подсписок кандидатов, начиная с [start ... n].
Для каждого из кандидатов мы вызываем рекурсивную функцию саму с обновленными параметрами.
Конкретно, мы добавляем текущего кандидата в комбинацию.
С добавленным кандидатом у нас теперь меньше суммы для выполнения, то есть remain - candidate.
Для следующего исследования мы все еще начинаем с текущего курсора start.
В конце каждого исследования мы делаем откат, удаляя кандидата из комбинации.
😎 Решение:
class Solution:
def combinationSum(self, candidates, target):
results = []
def backtrack(remain, comb, start):
if remain == 0:
results.append(list(comb))
return
elif remain < 0:
return
for i in range(start, len(candidates)):
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
backtrack(target, [], 0)
return results
Ставь 👍 и забирай 📚 Базу знаний