Generate Parentheses

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:

"((()))", "(()())", "(())()", "()(())", "()()()"

C++:
01 vector<string> generateParenthesis(int n) {
02        vector<vector <string> > A;
03        vector <string> t;
04        t.push_back(“”);
05        A.push_back(t);
06        for(int i=1;i<=n;i++){
07            vector <string> toAdd;
08            for(int j=0;j<i;j++){
09                vector <string>& first=A[j];
10                vector <string>& last=A[i1j];
11                for(int p=0;p<first.size();p++){
12                    for(int q=0;q<last.size();q++){
13                        string s=“(“+first[p]+“)”+last[q];
14                        toAdd.push_back(s);
15                    }
16                }
17            }
18            A.push_back(toAdd);
19        }
20        return A[n];
21 }
Advertisements
This entry was posted in Dynamic programming, String. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s