#include <stdio.h>
#include <stdlib.h>

/* CSSE, Monash University, Australia,  http://www.csse.monash.edu.au/ */
/* Generate All Strings Consisting of n Pairs of Matched Parentheses   */
/* (c) Tony Jansen, April 2001 */


void pb(int open, int closed, int index, char *s)
/* PRE: open >= closed >= 0 */
{
        if (open + closed == 0) {    /* none left to do, so done */
                printf("%s\n", s);
                return;
        }
        if (open == closed) {         /* only option is to add ( */
                s[index] = '(';
                pb(open-1, closed, index+1, s);
        }
        else if (open == 0) {         /* only option is to add ) */
                s[index] = ')';
                pb(open, closed-1, index+1, s);
        }
        else { /* assert: open > closed > 0 */
                s[index] = '(';                   /* try both ... */
                pb(open-1, closed, index+1, s);     /* ( ...  and */
                s[index] = ')';
                pb(open, closed-1, index+1, s);     /* ) ...      */
        }
}


int main(int argc, char *argv[])
{
        int     num;
        char    *s;

        if (argc != 2) {
                printf("Usage: program num_pairs_brackets\n");
                exit(0);
        }
        num = atoi(argv[1]);
        s = (char *) malloc (sizeof(char) * (2 * num + 1));
        s[2 * num] = '\0';

        pb(num, num, 0, s);

        return 0;
}