Сигнал задачи
Когда применять
Нужно исследовать выборы, отменяя изменения состояния.
Что держать в голове
- Уметь различать деревья решений подмножеств, комбинаций и перестановок.
- Уметь реализовывать choose-recurse-undo для перестановок.
Сложность
- В общем случае время экспоненциально — порядка O(b^d) для ветвления b и глубины d; стек и текущее состояние занимают O(d).
Границы и ошибки
- Каждое изменение состояния перед рекурсией должно быть симметрично отменено; иначе соседние ветви получают чужие решения.