Автор делится личным опытом решения задачи LeetCode на генерацию всех комбинаций правильных скобок. После неудачных собеседований он решил разобраться с backtracking и показал два подхода: через перебор всех комбинаций с отсеиванием и через рекурсию.
Статья даёт практическое понимание backtracking на примере конкретной задачи. Автор начинает с наивного перебора всех комбинаций, используя позиционные системы счисления для генерации N-мерных массивов, а затем отсеивает неподходящие по уровню вложенности.
После этого показывает рекурсивное решение, которое работает быстрее за счёт отсечения на ранних этапах. Будет полезно всем, кто готовится к собеседованиям с live-coding, особенно бэкендерам и Go-разработчикам
🔥Ссылка на статью
Заметки Бэкендера & Max