Here is a solution in C++. The main idea that I use is that I take the output from the previous i (where i is the number of bracket pairs), and feed that as input to the next i. Then, for each string in the input, we put a bracket pair at each location in the string. New strings are added to a set in order to eliminate duplicates.

#include <iostream> #include <set> using namespace std; void brackets( int n ); void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ); int main() { int n; cout << "Enter n: "; cin >> n; brackets(n); return 0; } void brackets( int n ) { set<string>* set1 = new set<string>; set<string>* set2; for( int i = 1; i <= n; i++ ) { set2 = new set<string>; brackets_aux( i, *set1, *set2 ); delete set1; set1 = set2; } } void brackets_aux( int x, const set<string>& input_set, set<string>& output_set ) { // Build set of bracket strings to print if( x == 1 ) { output_set.insert( "()" ); } else { // For each input string, generate the output strings when inserting a bracket pair for( set<string>::iterator s = input_set.begin(); s != input_set.end(); s++ ) { // For each location in the string, insert bracket pair before location if valid for( unsigned int i = 0; i < s->size(); i++ ) { string s2 = *s; s2.insert( i, "()" ); output_set.insert( s2 ); } output_set.insert( *s + "()" ); } } // Print them for( set<string>::iterator i = output_set.begin(); i != output_set.end(); i++ ) { cout << *i << " "; } cout << endl; }