Комбинации суммы

MediumАлгоритмы
05:00
Лучше работает на десктопе
BacktrackingRecursion

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

Один и тот же элемент можно использовать неограниченное число раз. Комбинации отсортированы лексикографически.

Сигнатура

def combination_sum(candidates: list[int], target: int) -> list[list[int]]:

Constraints

  • 1 ≤ len(candidates) ≤ 30
  • 2 ≤ candidates[i] ≤ 40
  • 1 ≤ target ≤ 40
  • Все candidates различны

Примеры

Пример 1

Вход:
candidates = [2,3,6,7]
target = 7
Выход:[[2,2,3],[7]]

Пример 2

Вход:
candidates = [2,3,5]
target = 8
Выход:[[2,2,2,2],[2,3,3],[3,5]]

Пример 3

Вход:
candidates = [2]
target = 1
Выход:[]
Консоль
Нажмите Run или Ctrl+Enter для запуска