Динамическое программирование отвечает на вопросы «сколько способов» и «какой максимум». Но иногда нужны не число, а сами варианты: все наборы сертификатов, дающие нужную сумму; все расстановки, все маршруты. Тут работает перебор с отсечением — организованный обход дерева вариантов, который вовремя бросает заведомо тупиковые ветки.
Дерево вариантов
Любой перебор можно представить деревом: в корне — пустое решение, на каждом уровне добавляется один элемент, в листьях — готовые варианты.
Соберём все наборы номиналов, дающие ровно нужную сумму. На каждом шаге решаем, какой номинал добавить следующим; сумма остатка уменьшается; дошли до нуля — набор готов, ушли в минус — тупик.
Обход такого дерева естественно пишется рекурсией: вызов = спуск на уровень ниже, возврат = подъём обратно.
Три обязательные части
Любой перебор с отсечением состоит из одного и того же.
Условие остановки — когда текущий набор уже является ответом (или уже безнадёжен).
Цикл по вариантам шага — что можно добавить прямо сейчас.
Откат — после возврата из рекурсии текущее состояние возвращают в исходный вид, чтобы попробовать следующий вариант на том же уровне. Это и есть «отступление», давшее приёму название.
static List<List<Integer>> combinations(int[] nominals, int target) {
int[] sorted = nominals.clone();
Arrays.sort(sorted);
List<List<Integer>> result = new ArrayList<>();
walk(sorted, 0, target, new ArrayDeque<>(), result);
return result;
}
static void walk(int[] nominals, int from, int rest, Deque<Integer> current, List<List<Integer>> result) {
if (rest == 0) {
result.add(new ArrayList<>(current));
return;
}
for (int i = from; i < nominals.length; i++) {
if (nominals[i] > rest) break;
current.addLast(nominals[i]);
walk(nominals, i, rest - nominals[i], current, result);
current.removeLast();
}
}
Пара строк current.addLast(...) и current.removeLast() — тот самый откат. Забыть вторую — самая частая ошибка приёма: набор будет накапливать мусор от соседних веток, и ответы поедут.
Вторая тонкость — new ArrayList<>(current) при сохранении ответа. Записать сам current нельзя: это изменяемый объект, который к концу перебора опустеет, и в результате окажется список пустых списков.
Отсечения — то, ради чего всё затевалось
Без отсечений перебор вариантов растёт лавинообразно и на сколько-нибудь заметном входе безнадёжен. Отсечение — это проверка, которая позволяет не спускаться в ветку, заведомо не содержащую ответов. В примере их два.
По значению. Строка if (nominals[i] > rest) break; обрывает цикл: данные отсортированы, и раз текущий номинал уже больше остатка, все следующие тем более не подойдут. Именно ради этого массив сортируют в начале.
По порядку. В рекурсию передаётся i, а не i + 1 и не ноль. Ноль разрешил бы возвращаться к прошлым номиналам, и наборы {2,3} и {3,2} считались бы разными. Передача i разрешает повторить тот же номинал, но запрещает идти назад — так каждый набор рождается ровно один раз.
Отсечения — это не оптимизация «на потом». Часто именно они отделяют работающее решение от зависающего.
Классический пример: ферзи
Расставить восемь ферзей на доске так, чтобы они не били друг друга. Полный перебор всех расстановок — это порядка четырёх миллиардов вариантов. Перебор с отсечением ставит ферзей по одному на строку и, прежде чем спуститься глубже, проверяет, не бьётся ли новый ферзь с уже поставленными. Ветка, где конфликт уже возник, обрывается сразу — и от четырёх миллиардов остаются тысячи проверок.
Мысль общая: чем раньше распознан тупик, тем больше дерева отсечено. Проверка «а есть ли ещё шанс» перед спуском окупается почти всегда.
Чем отличается от динамического программирования
Приёмы соседние, и выбирают между ними так.
Если нужны сами варианты — только перебор: список ответов физически негде «сложить в число».
Если нужно количество или лучший вариант, а подзадачи перекрываются, — берут динамическое программирование: оно не строит варианты, а сворачивает их в число, и потому куда быстрее.
Иногда приёмы совмещают: перебор с блокнотом посчитанного. Но если состояний столько же, сколько вариантов, запоминать нечего — перекрытия нет, и остаётся честный перебор.
Как узнать приём в задаче
- В условии просят перечислить все наборы, расстановки, маршруты, разбиения.
- Ответ — список списков, а не число.
- Размер входа маленький (десятки элементов): перебор по своей природе дорогой, и большие входы ему не по силам.
- Есть правило, по которому часть вариантов отсекается заранее.
Коротко
- Перебор с отсечением — обход дерева вариантов рекурсией с откатом состояния после каждой ветки.
- Три обязательные части: условие остановки, цикл по вариантам шага, откат изменений.
- Забытый откат и сохранение изменяемого объекта вместо копии — две самые частые ошибки.
- Отсечения решают всё: они превращают лавинообразный перебор в рабочий, обрывая заведомо тупиковые ветки.
- Передача текущего индекса вместо нуля не даёт получить один и тот же набор в разном порядке.
- Нужны сами варианты — перебор; нужно количество или максимум — динамическое программирование.
Дальше — как выбрать структуру данных: итоговое руководство по всему разделу.