Сумма комбинаций
Дан массив различных целых чисел nums и целевое число target. Необходимо вернуть список всех уникальных комбинаций чисел из nums, сумма которых равна target.
Каждое число из nums может быть использовано неограниченное количество раз. Две комбинации считаются одинаковыми, если частота использования каждого числа в них совпадает.
Комбинации в ответе могут быть возвращены в любом порядке, и числа внутри каждой комбинации также могут быть в любом порядке.
Пример 1:
Input: nums = [2,5,6,9] target = 9 Output: [[2,2,5],[9]] Объяснение: 2 + 2 + 5 = 9 (используем 2 дважды и 5 один раз) 9 = 9 (используем 9 один раз)
Пример 2:
Input: nums = [3,4,5] target = 16 Output: [[3,3,3,3,4],[3,3,5,5],[3,4,4,5],[4,4,4,4]]
Рекомендуемая сложность
Временная сложность решения будет экспоненциальной O(n^target), где n - размер массива nums, так как мы рассматриваем все возможные комбинации. Пространственная сложность O(target) для хранения текущей комбинации в рекурсии.
Подсказка 1
Подумайте об использовании рекурсии. Для каждого числа у нас есть выбор: либо включить его в текущую комбинацию и продолжить поиск с уменьшенной целью, либо пропустить его.
Подсказка 2
Используйте бэктрекинг для построения комбинаций. На каждом шаге либо берите текущее число и уменьшайте цель на его значение, либо переходите к следующему числу.
Подсказка 3
Чтобы избежать дубликатов в ответе, можно использовать индекс текущего числа и разрешать брать только числа начиная с этого индекса. Это гарантирует, что мы не построим одну и ту же комбинацию дважды.