#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

Good post and Smart Blog Thanks for your good information and i hope to subscribe and visit my blog STD Symptoms and more what causes Scabies ? thanks again admin