Код Senior Перебор с возвратом обновлено
Наборы с заданной суммой
Условие
Все уникальные наборы из candidates (каждое число можно брать сколько угодно раз) с суммой target. Наборы по возрастанию, без перестановок одного набора.
Примеры
combinationSum([2, 3, 6, 7], 7) // [[2, 2, 3], [7]]
combinationSum([2], 1) // []
combinationSum([2, 3], 6) // [[2, 2, 2], [3, 3]]
Как подойти
Параметр start отсекает перестановки: каждый набор порождается ровно один раз в неубывающем порядке. walk(i, …), а не walk(i+1, …), потому что число можно брать повторно. Обрезка по rest - ключевое отсечение, без него дерево перебора взрывается.
Подсказки: 2
- Чтобы не было перестановок одного набора, не возвращайся к уже пройденным индексам.
- Повторное использование числа - это рекурсия с тем же индексом, а не со следующим.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.