Предварительные обходы всех возможных двоичных деревьев при заданном обходе заказа

Я смотрел на вопросы о бинарных деревьях и наткнулся на следующее:
При заданном порядке обхода двоичного дерева выведите предварительные обходы всех возможных двоичных деревьев, удовлетворяющих указанному порядку обхода.

Например, если обход в порядке: {4, 5, 7}
Возможные деревья:

4         4           5         7       7
\          \       /   \      /       /
5          7     4     7    4       5
\        /                  \     /
7      5                    5   4

Поэтому обходы предварительного заказа:

4 5 7
4 7 5
5 4 7
7 4 5
7 5 4

Решение, которое я придумал:
Пройдите по указанному списку заказов. После каждой итерации выбирайте элемент из списка и делайте его корнем нашего дерева. Все элементы, предшествующие текущему, будут частью левого поддерева, а все последующие элементы будут образовывать правое поддерево. Затем мы можем рекурсивно сделать то же самое для левого и правого поддеревьев.

Например, в приведенном выше примере я начинаю с выбора 4 в качестве корня моего дерева. Теперь, так как перед 4 нет элементов, у меня не может быть левого поддерева. Я смотрю на остальные элементы. Они сформируют правильное поддерево. Я выбираю 5, чтобы быть корнем этого поддерева. Для этого мне остается только один выбор: построить правильное поддерево из 5 из 7. Это дает первое дерево примера.

Теперь я оставляю 4 в качестве корня, и вместо выбора 5 я выбираю 7 в качестве корня правого поддерева 4. Это приводит меня ко второму дереву примера выше.

Это хорошо. Проблема приходит с кодом. Я потратил довольно много времени на перевод вышеприведенного решения в код. Но я не был полностью успешным.

Вот что я пробовал в C ++:

void solve(vector<int> inOrder, int beg, int end, string &s, bool &flag)
{
for(int i = beg; i <= end; ++i)
{
s += to_string(inOrder[i]);
flag = false;
solve(inOrder, beg, i - 1, s, flag);
solve(inOrder, i + 1, end, s, flag);
if(s.size() == inOrder.size()) {flag = true; cout << s << endl;}
if(s.size() && flag) {s.pop_back();}
}
}

Я использую строку для хранения текущей перестановки элементов в обходе предварительного заказа. Элементы добавляются в строку, когда перестановка удовлетворяет прохождению по порядку.

Естественно, элементы должны быть впоследствии удалены из строки, чтобы освободить место для других перестановок. Тем не менее, я не смог выяснить, когда удалить элемент. В приведенном выше коде я добавляю элемент в первый раз, когда он встречается, и начинаю удалять элементы, когда строка имеет размер, равный размеру списка в заказе.

Итак, допустим, я начинаю с 4. Я добавляю 4 к строке. Я делаю то же самое для 5 и затем для 7. Теперь размер строки равен общему количеству элементов. Поэтому я удаляю последний. Моя строка сейчас 45, Поскольку с текущей строкой больше нет возможных комбинаций, я удаляю 5. У меня осталось 4. Теперь я могу добавить 7, а затем 5, что приводит к 475, Это прекрасно работает в этом случае, но я не смог заставить его работать для других комбинаций. Это не удается, когда я начинаю с 5 как корень, а не 4.

Итак, мой вопрос, как именно я должен приступить к решению вышеуказанной проблемы? Я даже делаю это правильно? Или я должен отказаться от этого подхода и подумать о чем-то еще? Если да, в каком направлении мне следует двигаться?

Я не ищу точное решение, только намек на то, что мне не хватает или что я могу сделать лучше.