Каждый шаг рекурсии — это ветка дерева. Вот как выглядит поиск чисел с суммой 3:
[] (сумма = 0)
┌────────┼────────┐
[1] [2] [3] ✔ (сумма=3, РЕШЕНИЕ!)
┌──┼──┐ ┌─┴─┐
[1,1] [1,2] [2,1] [2,2]✖ (сумма=4, отсечение)
┌┴┐ ✔ ✔
[1,1,1] [1,1,2]✖ [1,1,3]✖
✔ (сумма=4) (сумма=5)
(сумма=3)
Обозначения:
- ✔ — решение найдено (сумма = 3)
- ✖ — отсечение (сумма > 3)
- После каждой ветки происходит возврат к родителю
АЛГОРИТМ ПокажиДерево(решение, осталось, глубина)
отступ ← " " повторить глубина раз
ЕСЛИ осталось = 0 ТО
ВЫВЕСТИ отступ, "✔ РЕШЕНИЕ:", решение
ВЫЙТИ ИЗ АЛГОРИТМА
КОНЕЦ ЕСЛИ
ЕСЛИ осталось < 0 ТО
ВЫВЕСТИ отступ, "✖ отсечение"
ВЫЙТИ ИЗ АЛГОРИТМА
КОНЕЦ ЕСЛИ
ДЛЯ КАЖДОЙ цифры ИЗ [1, 2, 3] ВЫПОЛНЯТЬ
ВЫВЕСТИ отступ, "Добавляем", цифра
ДОБАВИТЬ цифру В КОНЕЦ решение
ПокажиДерево(решение, осталось - цифра, глубина + 1)
УДАЛИТЬ ПОСЛЕДНИЙ ЭЛЕМЕНТ ИЗ решение
ВЫВЕСТИ отступ, "Возврат, убираем", цифра
КОНЕЦ ЦИКЛА
КОНЕЦ АЛГОРИТМА
// Запуск
ПокажиДерево([], 3, 0)
Запусти алгоритм и нарисуй дерево на бумаге!