algorithmcatalan

Closure Number Method for Generate Parenthesis Problem

The standard Generate Parenthesis question on Leetcode is as follows

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

In the solution tab they have explained Closure Number Method which I am finding it difficult to understand.

I did a dry run of the code and even got the correct answer but can't seem to understand why it works? What is the intuition behind this method?

Any help would be greatly appreciated!

Solution

  • The basic idea of this algorithm is dynamic programming. So you try to divide your problem into smaller problems that are easy to solve. In this example you make the sub-problems so small that the solution is either an empty string (if the size is 0) or the solution is "()" (for the size 1).

    You start using the knowledge that if you want the parenthesis of a given length then the first character needs to be "(" and in some later place of the string there needs to be this character: ")". Otherwhise the output is not valid.

    Now you don't know the position of the closing parenthesis so you just try every position (the first for loop).

    The second thing you know, is that between the opening and the closing parenthesis and after the closing parenthesis there has to be something, that you don't realy know how it looks (because there are many possibilities), but it has to be a valid parenthesis pair again.

    Now this problem is just the problem you already solved. So you just put in every possibility of valid parenthesis (using a smaller input size). Because this is just what your algorithm already does you can use the recursive function call to do this.

    So summarized: You know a part of the problem, and that the rest of the problem is just the same problem with a smaller size. So you solve the small part of the problem you know and recursively call the same method to do this on the rest of the problem. Afterwards you just put it all together and got your solution.

    Dynamic programming is usually not that easy to understand but very powerfull. So don't wory if you don't understand it directly. Solving puzzles like these is the best way to learn dynamic programming.