Search code examples
algorithmdynamic-programmingcatalan

Dynamic Programming: Calculating kth parentheses sequence

An n parentheses sequence consists of n "("s and n ")"s.

A valid parentheses sequence is defined as the following:

You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.

For example, "(())" is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes "()", then you can make it empty. ")()(" is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes ")(" and you cannot erase any more.

Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.

For example, here are all valid 3 parentheses sequences in lexicographical order:

((()))
(()())
(())()
()(())
()()()

Source :https://code.google.com/codejam/contest/4214486/dashboard#s=p3

Note: Contest in now over and solutions are available to download.

I have solved it for small input ( k < 106 ) by using next_permutation() which is available in C++ STL. I am unable to formulate a sub problem for this. I have a tried to solve this by using Catalan's number but didn't seem to get any success. I don't want to see the solutions as it doesn't help in learning. Kindly help me in identifying a sub problem.

Solution

  • Let N denote the length of the sequence (i.e. 2 n).

    The key is to be able to count the number of valid sequences of length N.

    If you have a function, countValid(N, depth) you can solve the original problem as follows:

    1. If depth < 0 it's impossible (a negative depth means invalid sequence)

    2. If k < countValid(N-1, depth+1) append ( (because the sought sequence lies in the first half of the remaining search space)

    3. Otherwise append ) (because the sought sequence lies in the second half of the total search space)

    4. Continue from 1 with updated N-1 and depth+1 if you chose ( above, or depth-1 if you chose ) above.

    countValid(N, depth) can be implemented with dynamic programming with a standard DP matrix, M, with the two arguments as indexes:

    • The base case, M[0,0] = 1 since there is one valid 0-length sequence (the empty sequence)

    • For all other values in the first column M[0, 1...N] is 0.

    • For M[N,depth] you just add up

      • the number of valid sequences after opening: M[N-1, depth-1], and
      • the number of valid sequences after closing: M[N-1, depth+1]

      that is: M[N,depth] = M[N-1, depth-1] + M[N-1, depth+1]