Here's a simple backtracking algorithm. It starts with an empty list. It adds an left parenthesis. This is the root of the final tree. Then two options are possible, next parenthesis could be a left one or a right one, these are two branches. On the left branch we could again have a left or right parenthesis, on the right branch we already have a left and right parenthesis, so only another right parenthesis is possible. This tree of all possible solutions is navigated depth-first, and when a leaf is reached, the complete set of parentheses is printed out.
Here's the code. The recursion is what takes care navigate the tree of all possible combinations of parentheses.
#include
#include
#include
#include
#include
#include
#include
using namespace std;
void printParens(int p, int q, int n, char * A){
assert(p <= n && q <= n);
if (p == n && q == n){
for (int s = 0; s < 2*n; s++) cout << A[s] << "";
cout << endl;
return;
}
if (p + 1 <= n){
A[p + q] = '(';
printParens(p + 1, q, n, A);
}
if (q + 1 <= p){
A[p + q] = ')';
printParens(p, q + 1, n, A);
}
return;
}
int main() {
int n = 3;
char A[2*n];
printParens(0, 0, n, A);
return 0;
}