Решение задачи

Алгоритм решения задачи:

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

1) Определить состояния

Какое состояние нам нужно, чтобы знать, достигли ли мы решения (и использовать его для построения решения, если проблема требует этого).

Нам нужно состояние, чтобы отслеживать список букв, которые мы выбрали для текущей перестановки.

Какое состояние нам нужно, чтобы решить, какие дочерние узлы следует посетить следующими, а какие следует удалить?

Мы должны знать, какие буквы еще можно использовать (поскольку каждую букву можно использовать только один раз).

2) Нарисуем дерево состояний

3) DFS на дереве пространства состояний

Используя шаблон поиска с возвратом в качестве основы, мы добавляем два состояния, которые мы определили на шаге 1:

Список для представления перестановок, созданных на данный момент, путь

Список для записи того, какие буквы уже используются, used, used[i] == true означает, что i-я буква в исходном списке была использована.