All possible n pairs of balanced parentheses

#include <cstdio>
#include <list>
#include <string>
#include <iostream>
#include <iterator>
#include <algorithm>

using namespace std;


typedef list<string> List;

/*
Algo:
1. compute all possible balanced expressions of n-1 pairs
2. for each balanced expression of n-1 pairs
for each pos i from 0 to l of an expression
add '('
for each pos j from i + 1 to l
add ')' if expression is balanced
*/
List balParen(int n){

List l;

if(n == 1){

l.push_back("()");

} else if(n == 2){

l.push_back("()()");
l.push_back("(())");

}else {

List l2 = balParen(n - 1); //recursion


for(List::iterator it = l2.begin(); it != l2.end(); ++it){ //for each string of n - 1, add one more pair


for(int i = 0; i < it->length(); ++i){

string s = *it;

s.insert(i, "(");

int n = 0; //n == 0 shows balanced parenthesis

for(int j = i + 1; j < s.length(); ++j ){

if(n == 0){

string s2 = s;

l.push_back(s2.insert(j, ")"));
}

if(s[j] == '(') {

n++;

}else{
n--;
}
}

}
}
}

l.sort();

l.unique();

return l;

}

int main(){

int n;

scanf("%d", &n);

List l = balParen(n);

cout<<l.size()<<endl; //Catalan number Cn = (2n)! / ( (n+1)! n! )

copy(l.begin(), l.end(), ostream_iterator<string>(cout, "\n"));

return 0;
}
Advertisements

One thought on “All possible n pairs of balanced parentheses

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