1149. The kth Balanced Arrangement
A balanced arrangement uses n opening and n closing brackets, with every
closing bracket matched by an earlier opening one.
Given n and k, print the kth balanced arrangement in lexicographic order,
counting from 1. Note that ( sorts before ). If fewer than k arrangements
exist, print none.
Generating all 2^(2n) strings and testing each for balance works and does an
enormous amount of pointless work. The search can refuse to build an unbalanced
string in the first place.
Two counters are enough. An opening bracket may be added while fewer than n
have been used. A closing bracket may be added only while fewer have been used
than openings, because closing more than you have opened can never recover.
Trying the opening bracket before the closing one at every step produces
lexicographic order directly, so the kth arrangement is simply the kth one
the search reaches.
Constraints - `1 ≤ n ≤ 10` - `1 ≤ k ≤ 100000`
Input
A single line containing two integers n and k.
Output
Print the kth balanced arrangement in lexicographic order, or none if fewer than k exist.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.