generate paren

print_paren.c

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

#define MAX(A, B) ((A)>(B)?(A):(B))

static void print_paren(int n);
static void do_print(int n, int* idx, int k);
static void print_result(int n, int* idx);

int main(int argc, char** argv) {
    assert(argc==2);
    int count = atoi(argv[1]);
    print_paren(count);
}

static void do_print(const int n, int* idx, const int k) {
    if (k == n) {
        print_result(n, idx);
    } else {
        int from = k;
        if (k > 0) {
            from = MAX(from, idx[k-1]);
        }
        for (int i=from; i<n; ++i) {
            idx[k] = i;
            do_print(n, idx, k+1);
        }
    }
}

static void print_result(const int n, int* idx) {
    int iter = 0;
    for (int i=0; i<n; ++i) {
        putchar('(');
        while (iter < n && idx[iter] == i) {
            putchar(')');
            iter++;
        }
    }
    putchar('\n');
}

static void print_paren(const int n) {
    assert(n >= 0);
    int* idx = (int*) malloc(sizeof(int)*n);
    assert(idx != NULL);
    if (n == 0) {
        printf("\n");
    } else {
        do_print(n, idx, 0);
    }
    free(idx);
}