Leetcode.com problem 22: "Generate-Parentheses"

James S. Plank

Tue Aug 23 10:26:45 EDT 2022

Problem Statement.
A skeleton with a main() that reads problems from stdin.
tests.sh -- Testing script.
answers.txt -- Correct output of the testing script.
This is a "medium" problem.
Success Rate (as of August, 2022): 71.2%

In case Leetcode's servers are down

Implement generateParenthesis() in the following class:

class Solution {
public:
    vector<string> generateParenthesis(int n);
};

The goal is to enumerate all parenthesis strings that are "valid", and have n sets of parentheses. The following defines "valid":

"" and "()" are valid.
If A is valid, then "(A)" is valid.
If A and B are valid, then AB is valid.

n is constrained to be between 1 and 8.

The examples

The tests.sh script tests every value of n from 1 to 8:

echo 1 | ./a.out
echo ""
echo 2 | ./a.out
echo ""
echo 3 | ./a.out
echo ""
echo 4 | ./a.out
echo ""
echo 5 | ./a.out
echo ""
echo 6 | ./a.out
echo ""
echo 7 | ./a.out
echo ""
echo 8 | ./a.out

So, you can see the correct answers in answers.txt

()

(())
()()

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

etc.

Hints

As with many enumerations, this one feels like it should be solved recursively. I tried a simple recursion and couldn't get it right, so instead I decided to maintain two data structures:

All. This is a vector of vectors of strings. All[n] contains the answer for n.
Simple. This is another vector of vectors of strings. All[n] contains all of the strings in All[n] that are of the form "(A)". In other words, "(()())" is in simple[3] and all[3], but "()()()" is only in all[3].

You can start by putting "" into all[0] and simple[0]. Now, when you are confronted with building all[n] and simple[n], you first build all[n-1] and simple[n-1]. Then, it should be clear to see how you build simple[n] from all[n-1].

To build all[n], you can use the following technique:

Add all concatenations of strings from simple[n] and all[0]. (Those will simply be all strings from simple[n].
Then add all concatenations of strings from simple[n-1] and all[1].
Then add all concatenations of strings from simple[n-2] and all[2].
Etc, stopping at simple[1].

To see this in progress, suppose you need all[3]. You can see from the answers.txt file above that:

all[0] =    [ "" ]
simple[0] = [ "" ]

all[1] =    [ "()" ]
simple[1] = [ "()" ]

all[2] =    [ "(())", "()()" ]
simple[2] = [ "(())" ]

So, you construct simple[3] from all[2]:

simple[3] =    [ "((()))", "(()())" ]

And now you construct all[3] from the lop above:

all[3] =  [ "((()))", "(()())"       # Concatenations of simple[3] and all[0]
            "(())()",                # Concatenations of simple[2] and all[1]
            "()(())", "()()()" ]     # Concatenations of simple[1] and all[2]

Go ahead and solve the problem!