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;
}
Comments