Combination Sum

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

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

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

+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]]
Пояснение: Четыре двойки дают 8, как и 2 + 3 + 3 и 2 + 6. Все три варианта начинаются с 2, поэтому порядок задаёт второе значение: 2, затем 3, затем 6. Без 2 остаются только 3 и 6, а любая их комбинация кратна 3, а 8 не кратно 3.

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

Ввод: candidates = [4, 9]target = 9
Вывод: [[9]]
Пояснение: 9 само по себе является комбинацией. Шаги по 4 дают только 4, 8 и 12, проходя мимо 9, а 4 + 9 — это уже 13, поэтому [9] — единственный ответ.

+12 скрытых тестов при отправке

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

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

Подсказки

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

Открыто 0 из 3

Решение

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

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

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

Идея

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

Представьте дерево решений, в котором после сортировки на каждого кандидата приходится один уровень. На уровне i вы решаете, сколько копий i-го значения взять, а каждый лист внизу представляет собой полный набор выбранных количеств. У каждого мультимножества есть ровно один список количеств, поэтому ни одна комбинация не будет найдена дважды. Перебор, начиная с наибольшего количества, также обеспечивает требуемый порядок: если два ответа впервые различаются количеством некоторого значения, то в том из них, где этого маленького значения больше, оно всё ещё присутствует, тогда как в другом уже присутствует большее значение, поэтому этот ответ идёт первым.

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

Алгоритм

Отсортируй кандидатов и создай массив счётчиков, по одному на каждое значение.
Напиши choose(i, total), которая фиксирует количество значения с индексом i.
Для k от target / nums[i] до 0 установи счётчик равным k и вызови 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], поскольку кандидат может повторяться, или любое более позднее значение, но никогда не более раннее. Поэтому вызов, добавивший индекс i, выполняет цикл только от i и далее. У каждой комбинации есть ровно один порядок возрастания, значит, в дереве ей соответствует ровно один путь, и дубликат вроде [3, 2, 3] никогда не будет построен.

Вот всё дерево для отсортированного массива [2, 3, 6] и целевого значения 8. В корне остаётся 8; там перебираются 2, 3 и 6. После 2 остаётся 6. После 2, 2 остаётся 4, а после 2, 2, 2 остаётся 2 — ещё одна 2 даёт ответ [2, 2, 2, 2]; после 2, 2, 3 остаётся 1, и эта ветвь завершается. После 2, 3 остаётся 3; можно попробовать только 3 и 6, и 3 даёт [2, 3, 3]. После 2, 6 ничего не остаётся: [2, 6]. После 3 можно попробовать только 3 и 6, а после 3, 3 остаётся 2, которое ни одно из них не заполняет. После 6 остаётся 2, и можно попробовать только 6. Всего двенадцать вызовов вместо 30 листьев в первом подходе.

Сортировка превращает тупиковую ветвь в условие для ранней остановки. Когда nums[i] больше остатка, все последующие значения тоже будут больше, поэтому цикл завершается с помощью break, вместо того чтобы проверять остальные. В дереве выше узел 2, 2, 3 с остатком 1 проверяет 3, видит, что оно не подходит, и больше не проверяет 6. Поиск посещает только префиксы, сумма которых всё ещё не превышает target, поэтому большие тесты, на которых первый подход терпит неудачу, здесь требуют всего несколько тысяч вызовов.

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

Алгоритм

Отсортируй кандидатов по возрастанию.
Напиши backtrack(start, remaining), которая использует один список path. Если remaining равен 0, сохрани копию path.
В противном случае перебирай i от start до конца. Если nums[i] > remaining, выполни break: все последующие значения больше.
Добавь nums[i], вызови backtrack(i, remaining-nums[i]), передав i, а не i + 1, чтобы значение могло повторяться, а затем удали его.
Вызови 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 для кандидатов, которые вы не отсортировали. Для [6, 2, 3], если осталось 2, цикл остановится на 6 и так и не проверит 2.
Возврат комбинаций в порядке, заданном неотсортированным входным списком. Ожидаемый список упорядочен лексикографически, и отсортированный поиск обеспечивает этот порядок без дополнительной сортировки.
В Lua и R массивы начинаются с 1, поэтому первый вызов начинается с индекса 1, а цикл выполняется до длины массива.

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

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

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

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

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

Как избежать повторяющихся комбинаций без множества?

Генерируйте все комбинации в одном фиксированном порядке, по возрастанию. Начальный индекс обеспечивает это: после добавления nums[i] поиск рассматривает только nums[i] и следующие значения. Таким образом, для каждой комбинации есть ровно один путь в дереве поиска, поэтому она создаётся один раз, и множество или финальное удаление дубликатов не требуется.

Можно ли решить задачу «Сумма комбинаций» с помощью динамического программирования?

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

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

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