Комбинации с заданной суммой
Условие
Массив уникальных положительных чисел и целевое число. Верни все комбинации без повторений чисел внутри комбинации, дающие в сумме целевое. Комбинации уникальны, порядок внутри - возрастающий.
Что проверяют тесты
базовый случай
число целиком
нет решений
числа не повторяются в комбинации
несколько комбинаций
Как подойти
Отличие от классической combination sum: здесь число берётся максимум один раз, поэтому рекурсия с i+1, а не с i. Сортировка нужна не для порядка вывода, а для отсечения: как только текущее число больше остатка, все следующие тоже больше, и цикл можно прервать. Без отсечения дерево перебора растёт экспоненциально на больших входах.
Подсказки: 3
- Каждое число можно взять не более одного раза - рекурсия идёт с i+1.
- Сортировка позволяет обрывать перебор, как только число превысило остаток.
- Сохраняй копию текущей комбинации, а не ссылку.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.