Вопрос интервью, рекурсия + отслеживание с возвратом

Этот вопрос был задан в интервью и касается рекурсии / отслеживания с возвратом. у нас есть два массива логических значений: bool * source и bool * target , каждый из них одинаковой длины n (source / target / n задаются как аргументы Задача вопроса - преобразовать источник в цель с помощью операции переключателя .

• Если есть несколько преобразований: представить любое из них
• Если нет решения: заявить, что решения нет

Определение: операция switch (int i, bool * arr) инвертирует значение в arr [i] и arr [i-1] и arr [i + 1] (если эти индексы находятся в диапазоне 0 ... n-1).

Другими словами, операция switch обычно меняет три бита ( i и его соседи), но только два на концах.

Например, достаточно: переключатель

• (0, arr) переключает значения arr [0] и arr [1], только переключатель
• (n-1, arr) переключает значения arr [n-1] и arr Только [n-2]

Заранее благодарим вас за предложения по алгоритму.