Permutations with parenthesis

Find all valid permutations of N parenthesis.  For example if N = 2, the following permutations are possible - {{}}, {}{}

/*

 * PermutationsWithParenthesis.cpp

 *

 *  Created on: May 14, 2012

 *      Author: Kiran Hegde

 */

#include <iostream>

#include <string>

#include <vector>

using namespace std;

void addParenthesis(int leftParens, int rightParens,

        string str, vector<string> &output) {

    if (leftParens < 0 || rightParens < 0) {

        return;

    }

    if (leftParens == 0 && rightParens == 0)

        output.push_back(str);

    else {

        if (leftParens > 0) {

            addParenthesis(leftParens-1, rightParens, str + "{", output);

        }

        if (rightParens > leftParens) {

            addParenthesis(leftParens, rightParens-1, str + "}", output);

        }

    }

}

void createParenthesis(int noParenPairs, vector<string> &output) {

    addParenthesis(noParenPairs, noParenPairs, string(""), output);

}

/**

 * Test the code

 */

int main() {

    vector<string> parenList;

    int noOfParenPairs = 3;

    createParenthesis(noOfParenPairs, parenList);

    cout << "Permutations with " << noOfParenPairs

            << " pairs of parenthesis: " << parenList.size() << endl;

    for (unsigned int i=0; i<parenList.size(); i++) {

        cout << parenList[i] << endl;

    }

    return 0;

}