Перестановки, зависящие от регистра символа. Решение задачи.

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