#include <string>
#include <vector>
#include <iostream>

using namespace std;

//  There are two solutions for this problem, one is simple Backtracing(Bt), the other is 
//  Dynamic Programming(DP). I was thinking the DP would be faster when the Parentheses 
//  become larger.
//  However, after test with 15+, it comes out Bt is much faster than DP.
//  
//  The reseaon here may because the result is not just one, it would takes much more times
//  generate inner results (we see for loop with push_back in DP).
//  
//  DP may faster than Bt, when we need results that less than MAXNUM again and again, for
//  This situation, we do not need to calculate again.


/********************* Backtracing Solution *********************/

vector<string> result;
void GenerateParentheses(string& p, int left, int right, int level)
{
	if (left == 0 && right == 0) 
    {
        result.push_back(p);
        return;
    }
	
    //Append left parenthese
    if (left > 0)
    {
        p[level] = '(';
        GenerateParentheses(p, left-1, right+1, level+1);
    }
	
    //Append right parenthese
    if (right > 0)
    {
        p[level] = ')';
        GenerateParentheses(p, left, right-1, level+1);
    }
}

void GenerateParentheses(int n)
{
    //initialize length of string to 2*n 
    string parenthesis(n*2,'\0');
	result.clear();
    GenerateParentheses(parenthesis, n, 0, 0);
}

/********************* Dynamic Programming Solution *********************/

#define MAXNUM 100

vector<string> dp[MAXNUM][MAXNUM];  //half of the array is not used

void GenerateParentheses(int left, int right)
{
    if (left == 0 && right == 0) 
    {
        dp[0][0].push_back("");
        return;
    }
    
    //Append left parenthese
    if (left > 0)
    {
        vector<string>& strs = dp[left-1][right+1];
        if (strs.size() <= 0)
            GenerateParentheses(left-1, right+1);
        
        for (int i = 0; i < strs.size(); ++i)
            dp[left][right].push_back('(' + strs[i]);
    }
    
    //Append right parenthese
    if (right > 0)
    {
        vector<string>& strs = dp[left][right-1];
        if (strs.size() <= 0)
            GenerateParentheses(left, right-1);
		
        for (int i = 0; i < strs.size(); ++i)
            dp[left][right].push_back(')' + strs[i]);
    }
}

vector<string>& GenerateParentheses_dp(int n)
{
    if (dp[n][0].size() <=0 )
        GenerateParentheses(n, 0);
	
    return dp[n][0];
}

int main(int argc, char** argv)
{
	//The first result maybe slow, but the rest is very fast
	for (int i = 13; i > 0; --i)
	{
		int n = i;
		GenerateParentheses(n);
		GenerateParentheses_dp(n);
		
		cout << n <<": ";
		if (result == dp[n][0])
			cout << "The same result for Backtracing and Dynamic Programming\n";
		else
			cout << "Different!!!!!!!!";
	}
	
    // for (int i = 0; i < result.size(); ++i)
    //     cout<<result[i] << '\n';
	
	return 0;
}