Выбор ответа Middle Перебор с возвратом обновлено
Отсечение в сумме комбинаций
Вопрос
Ищем комбинации с суммой target из положительных чисел. Какое отсечение корректно и полезно?
Попробуйте сами
Выберите вариант, и откроется разбор.
Показать ответ и разбор
Коротко
Правильный ответ: Остановиться, когда сумма превысила target, а после сортировки делать break. Числа положительные, сумма только растёт: превысив target, ветка безнадёжна.
Варианты ответа
- Остановиться, когда сумма превысила target, а после сортировки делать
breakправильный ответ - Остановиться, когда длина пути больше 2: длинные пути не дают новых сумм
- Отсекать ветку, когда текущая сумма ещё меньше target и элементы кончаются
- Отсечения невозможны: без полного перебора легко пропустить нужную комбинацию
Разбор
Числа положительные, сумма только растёт: превысив target, ветка безнадёжна. После сортировки, если nums[j] уже не влезает, не влезут и все следующие, можно break.
- Ограничение длины неверно: решения бывают длинными.
- Сумма меньше target это нормальное промежуточное состояние.
- Отсечения возможны, как показано.
Ответьте сами, а не прочитайте
В тренажёре вопрос попадёт в повторения и вернётся, когда начнёт забываться. Плюс билеты с зачётом: 20 вопросов, не больше 2 ошибок.