Спасибо, помогло разобраться. Хотя я почти сам к такому решению пришел, но из-за того, что при передаче аргументов присваивал им значения в текущем стековом кадре, вместо того чтобы передать + 1 без присваивания, то я тупил сильно почему не получается ))) ееее
@@SurenKhorenyan В любом случае: О(2^(2*N)) = O(2^2 * 2^N) = O(4 * 2^N) = O(2^N) O(2^N) потому что на каждом шаге бэктрекинга мы заходим в него 2 раза (в худшем случае). Вот и получается что 2*2*2*...*2 в количестве N раз. P.S. хотел написать ответом на комментарий, но получилось Вам, Сурен. :D Спасибо за видео!
Привет, спасибо за объяснение, но я все еще путаюсь как твой код понимает что теперь такую комбинацию надо делать, а не условно только "((()))", объясни пожалуйста
Привет! Рад помочь. Мы сначала добавляем один элемент, а затем смотрим, какие комбинации дальше вообще возможны. По сути, перебираем все валидные варианты. Начинаем с пустой строки и дальше проверяем, можем ли что-то добавить? В пустой строке можно начать только с открывающей скобки. Дальше можно либо закрыть, либо открыть новую.. и так далее. А в коде это происходит за счёт рекурсивного вызова backtrack. Мы меняем состояние текущего экземпляра, и следующий вызов смотрит, какие скобки мы уже открыли
Огромное спасибо чувак за видео, оно сделало мне день и дало мотивации дальше грокать задачи!
Класс, очень рад помочь! Спасибо за такой приятный отзыв 🥰
Спасибо, помогло разобраться. Хотя я почти сам к такому решению пришел, но из-за того, что при передаче аргументов присваивал им значения в текущем стековом кадре, вместо того чтобы передать + 1 без присваивания, то я тупил сильно почему не получается ))) ееее
Ура! Круто, что удалось разобраться! Рад помочь 😊
Привет! спасибо за видео. А какая будет пространственная и временная сложность у этого алгоритма?
Привет! Пожалуйста!
По пространству тут O(n), а вот по времени либо O(2^N), либо O(2^2N), что-то такое
@@SurenKhorenyan В любом случае: О(2^(2*N)) = O(2^2 * 2^N) = O(4 * 2^N) = O(2^N)
O(2^N) потому что на каждом шаге бэктрекинга мы заходим в него 2 раза (в худшем случае). Вот и получается что 2*2*2*...*2 в количестве N раз.
P.S. хотел написать ответом на комментарий, но получилось Вам, Сурен. :D
Спасибо за видео!
@@rememberme8869 спасибо за уточнение!
И пожалуйста 🥰
Привет, спасибо за объяснение, но я все еще путаюсь как твой код понимает что теперь такую комбинацию надо делать, а не условно только "((()))", объясни пожалуйста
Привет! Рад помочь.
Мы сначала добавляем один элемент, а затем смотрим, какие комбинации дальше вообще возможны. По сути, перебираем все валидные варианты. Начинаем с пустой строки и дальше проверяем, можем ли что-то добавить? В пустой строке можно начать только с открывающей скобки. Дальше можно либо закрыть, либо открыть новую.. и так далее. А в коде это происходит за счёт рекурсивного вызова backtrack. Мы меняем состояние текущего экземпляра, и следующий вызов смотрит, какие скобки мы уже открыли