Combination Sum

Q: Какова временная сложность задачи «Сумма комбинаций»?

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

Q: Почему в Combination Sum вы вызываете рекурсию с i, а не с i + 1?

Рекурсия с i позволяет следующему значению снова быть тем же кандидатом — так значение можно использовать более одного раза. Рекурсия с i + 1 переходит дальше, поэтому каждый кандидат можно использовать не более одного раза.

Q: Можно ли решить задачу Combination Sum с помощью динамического программирования?

Да. Для каждой суммы от 0 до target сохраняй комбинации, которые её дают, добавляя по одному кандидату за раз, чтобы каждый список оставался отсортированным по возрастанию. Алгоритм никогда не исследует тупиковый путь дважды, но хранит каждую частичную комбинацию для каждой суммы, что требует гораздо больше памяти. Поскольку объём вывода сам по себе может быть экспоненциальным, обычно используют алгоритм с возвратом.

СреднеПоиск с возвратом

+10

Дан список различных положительных целых чисел candidates и положительное целое число target. Найдите все комбинации чисел из списка, сумма которых в точности равна target. Каждое число можно использовать любое количество раз. [2, 3, 3] и [3, 2, 3] — это одна и та же комбинация.

Верните каждую комбинацию в порядке возрастания, а сами комбинации — в лексикографическом порядке: на первой позиции, где две комбинации различаются, сначала должна идти комбинация с меньшим значением.

Функция

combinationSum(candidates: integer-array, target: integer) → integer-2d-array

candidatesinteger-array: различные значения, которые вы можете использовать в любом порядке и любое количество раз
targetinteger: общая сумма каждой комбинации должна быть ровно
Возвращаетinteger-2d-array: все комбинации, сумма которых равна целевому значению, каждая в порядке возрастания, перечисленные в лексикографическом порядке

Ограничения

1 ≤ candidates.length ≤ 50
2 ≤ candidates[i] ≤ 500
2 ≤ target ≤ 500
Все значения в candidates различны и не упорядочены.
Не менее одной комбинации достигает target, и не более 150 комбинаций делают это.

Примеры

Ввод: candidates = [6, 2, 3]target = 8
Вывод: [[2, 2, 2, 2], [2, 3, 3], [2, 6]]
Пояснение: Четыре двойки, 2 + 3 + 3 и 2 + 6 — всё это даёт 8, в порядке возрастания второго значения. Без двойки остаются только тройки и шестёрки, а их суммы кратны 3, чему число 8 не соответствует.

Ввод: candidates = [5, 3, 4]target = 11
Вывод: [[3, 3, 5], [3, 4, 4]]
Пояснение: 3 + 3 + 5 и 3 + 4 + 4 дают 11, а [3, 3, 5] идет первым, потому что его второе значение, 3, меньше 4. Ни одна комбинация только из 4 и 5 не дает 11.

Дополнительный вопрос

Теперь каждый кандидат можно использовать не более одного раза, а candidates может содержать повторяющиеся значения. Как изменить поиск, чтобы одна и та же комбинация не появлялась дважды?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Ловушка — построить одну и ту же комбинацию дважды: 2, 3, 3 и 3, 2, 3 — это один и тот же ответ. Строй каждую комбинацию в порядке возрастания, чтобы у неё был ровно один путь, и сортируй кандидатов, чтобы ветвь останавливалась, как только следующее значение становится больше оставшейся суммы.

Попробуйте каждое количество для каждого кандидата

Верно, но не успевает на самых больших тестах

Идея

Комбинация полностью описывается количеством копий каждого кандидата: [2, 3, 3] — это одна 2, две 3 и ни одной 6. Перебери каждое количество для каждого отсортированного кандидата — от target / c до 0 — и оставляй варианты, сумма которых в точности равна target. У каждой комбинации есть единственный список количеств, поэтому ни одна не найдётся дважды. Перебор от больших количеств к меньшим задаёт лексикографический порядок: если два ответа впервые различаются в некотором значении, то в ответе с большим количеством копий это значение сохраняется, а в другом ответе на его месте стоит большее значение.

Для [2, 3, 6] и цели 8 есть 5 × 3 × 2 = 30 листьев для 3 ответов. Каждый кандидат, больший, чем target / 2, удваивает количество листьев, поэтому 40 таких кандидатов означают 2^40, то есть примерно 10^12.

Алгоритм

Отсортируйте кандидатов и храните по одному счётчику для каждого значения.
В choose(i, total) перебирайте каждое количество k от target / nums[i] до 0 и вызывайте choose(i + 1, total + k × nums[i]).
Когда для каждого значения будет определено количество, сохраните комбинацию, если total равно target, и сформируйте её на основе счётчиков.
Вызовите choose(0, 0).

def combinationSum(candidates, target):
    nums = sorted(candidates)
    counts = [0] * len(nums)
    result = []

    def choose(i, total):
        if i == len(nums):
            if total == target:
                combo = []
                for value, k in zip(nums, counts):
                    combo.extend([value] * k)
                result.append(combo)
            return
        # Most copies first, so the combinations come out in lexicographic order.
        for k in range(target // nums[i], -1, -1):
            counts[i] = k
            choose(i + 1, total + k * nums[i])
        counts[i] = 0

    choose(0, 0)
    return result

Возвращайтесь назад в порядке возрастания и отсекайте

Идея

После того как ты добавишь nums[i], следующим значением может быть снова nums[i] или любое более позднее значение, но не более раннее. У комбинации есть ровно один порядок по возрастанию, поэтому для неё есть ровно один путь, а [3, 2, 3] никогда не будет построена.

Для отсортированного массива [2, 3, 6] и целевого значения 8 пути 2, 2, 2, 2 и 2, 3, 3, и 2, 6 дают в сумме 8. На пути 2, 2, 3 остаётся 1, и поиск останавливается, не проверяя 6; после 3, 3 остаётся 2, которому не подходит ни одно значение. Это 12 вызовов против 30 листьев при подсчёте.

На каждом уровне цикл сначала перебирает меньшие значения, поэтому ответы появляются в лексикографическом порядке. Ни один ответ не является префиксом другого, поскольку значения положительны и оба дают одну и ту же сумму.

Алгоритм

Отсортируй кандидатов.
В backtrack(start, remaining) сохрани копию общего path, если remaining равен 0.
Иначе перебирай i, начиная с start. Если nums[i] > remaining, выйди из цикла: все последующие значения больше.
Добавь nums[i], вызови backtrack(i, remaining - nums[i]), затем удали его.
Вызови backtrack(0, target) и верни сохранённые комбинации.

def combinationSum(candidates, target):
    nums = sorted(candidates)
    result = []
    path = []

    def backtrack(start, remaining):
        if remaining == 0:
            result.append(path[:])
            return
        for i in range(start, len(nums)):
            if nums[i] > remaining:
                break  # sorted, so every later value is too big as well
            path.append(nums[i])
            backtrack(i, remaining - nums[i])  # i, not i + 1: nums[i] may repeat
            path.pop()

    backtrack(0, target)
    return result

Ловушки и крайние случаи

Перебор каждого кандидата на каждом уровне вместо перебора, начиная с текущего индекса. Тогда [2, 3, 3], [3, 2, 3] и [3, 3, 2] будут выданы как три ответа.
Рекурсивный вызов с i + 1 вместо i. Тогда каждое значение может встретиться только один раз, поэтому [2, 2, 2, 2] пропадёт.
Сохранение самого path, а не его копии. Тогда каждый сохранённый ответ будет одним и тем же списком, который алгоритм с возвратом очистит к концу.
Использование break для кандидатов, которые не были отсортированы. Если осталась сумма 2, а список — [6, 2, 3], цикл остановится на 6 и так и не попробует 2.

Частые вопросы3

Какова временная сложность задачи «Сумма комбинаций»?

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

Почему в Combination Sum вы вызываете рекурсию с i, а не с i + 1?

Рекурсия с i позволяет следующему значению снова быть тем же кандидатом — так значение можно использовать более одного раза. Рекурсия с i + 1 переходит дальше, поэтому каждый кандидат можно использовать не более одного раза.

Можно ли решить задачу Combination Sum с помощью динамического программирования?

Да. Для каждой суммы от 0 до target сохраняй комбинации, которые её дают, добавляя по одному кандидату за раз, чтобы каждый список оставался отсортированным по возрастанию. Алгоритм никогда не исследует тупиковый путь дважды, но хранит каждую частичную комбинацию для каждой суммы, что требует гораздо больше памяти. Поскольку объём вывода сам по себе может быть экспоненциальным, обычно используют алгоритм с возвратом.

def combinationSum(candidates, target):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргументы

candidates = [6, 2, 3]
target = 8

Ожидаемый вывод

[[2, 2, 2, 2], [2, 3, 3], [2, 6]]