Combination Sum

Средняя№39выбор с повтором

Дан список разных положительных чисел, кандидатов, и целевая сумма. Нужно вернуть все наборы кандидатов, которые в сумме дают цель, причём кандидата можно брать сколько угодно раз; наборы из тех же чисел в другом порядке считаются одним. Наш пример: [4, 5, 3] и 8 дают [3, 5] и [4, 4].

39 Combination SumРазбор · 1×

Пример: суммы 8 из [4, 5, 3]. Смотрите на [3, 3], когда осталось 2: 3 уже слишком много, поэтому цикл сразу прерывается — 4 и 5 после неё ещё больше.

[ ]33,33,43,544,45кандидаты041523путь—результаты—
ещё не былипо пути сюдаэтот шагдаёт цель или ведёт к набору, который даётотрезано: больше, чем осталосьтупик, или до start: недоступно

Ищем все способы набрать 8 из [4, 5, 3], каждое число сколько угодно раз

01/36
сначала · назад · пуск · шаг
Скорость
1function combinationSum(candidates, target):
2 sort(candidates)
3 path = []
4 results = []
5 pick(0, target)
6 return results
7
8function pick(start, left):
9 if left == 0:
10 add copy of path to results
11 return
12 for i from start to len(candidates) - 1:
13 if candidates[i] > left: break // rest bigger
14 path.add(candidates[i])
15 pick(i, left - candidates[i]) // reuse allowed
16 path.removeLast()
состояние
candidates
[4, 5, 3]
start
–
left
–
i
–
path
–
results
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Вызов ниже получает i, а не i + 1, поэтому тот же кандидат можно взять ещё раз, как в [4, 4]; индекса меньше i он не получает, поэтому каждый набор собирается в одном порядке, от меньшего к большему, и [5, 3] не повторяет [3, 5].
  2. Все кандидаты положительные, поэтому left только уменьшается: при left = 0 путь — это ответ, а путь, у которого следующий кандидат больше left, до цели уже не дойдёт.
  3. После сортировки первый кандидат больше left означает, что и все следующие больше, поэтому break отрезает весь остаток цикла, а не проверяет каждого.

Сложность

Время O(n^(t / m) × t / m) в худшем случае, где t — цель, а m — наименьший кандидат: в пути не больше t / m чисел, каждое выбирается из не более чем n, и каждый ответ копируется. Память O(t / m) помимо ответа: путь и стек вызовов.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.