А ты не возвращай строку, сильно ненадёжно
Есть внешний публичный метод, который возвращает то, что нужно по заданию (строку)
Есть внутренняя рекурсивная функция, которая с помощью параметров и возвращаемого значения позволяет "вспомнить" состояние и раскрутить решение, если оно нашлось