Найти k-ю последовательность правильных скобок
Я пытаюсь решить довольно сложную проблему с помощью скобок.
Давайте определим правильную последовательность скобок, если:
- Строка пуста
- Строка имеет вид (B), где B - правильная скобочная последовательность.
- Строка имеет форму LR, где L и R являются действительными последовательностями скобок.
Скажем теперь, что у нас есть два целых числа N и K. Определим последовательность скобок типа N, которая имеет ровно N '(', открытые скобки и точно N ')', закрытые скобки. Наша задача - найти последовательности скобок K, если последовательности скобок упорядочены в лексикографическом порядке.
Ограничения
N <= 100
К <= 10^18
пример
Допустим, N = 3, у нас есть 5 правильных скобочных выражений.
- ((()))
- (() ())
- (()) ()
- () (())
- () () ()
Наша задача - вернуть K-ю последовательность из этого заказа.
Что я думаю для решения
Я думаю, что мы должны сначала сделать некоторые вычисления с динамическим программированием, а затем вернуть K-ю перестановку. Тем не менее, я застрял с расчетами динамического программирования. Заранее спасибо.