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