程序代码：

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

#define N 1000
int d[N] = {}, n;

void printans()
{
    int i, j;

    for (i = 0; i < n; ++i)
    {
        if (d[i] > 0)
        {
            for (j = 0; j < d[i]; ++j) printf("(");
            printf("%c", 'A' + i);
        }
        else if (d[i] < 0)
        {
            printf("%c", 'A' + i);
            for (j = d[i]; j < 0; ++j) printf(")");
        }
    }
    printf("\n");
}

void solve(int start, int end)
{
    if (start == 0 && end == n - 1)
    {
        printans();
        return;
    }

    if (start > 0)
    {
        start -= 1; d[start] += 1; d[end] -= 1;
        solve(start, end);
        d[end] += 1; d[start] -= 1; start += 1;
    }

    if (end < n - 1)
    {
        end += 1; d[start] += 1; d[end] -= 1;
        solve(start, end);
        d[end] += 1; d[start] -= 1; end -= 1;
    }
}

int main(void)
{
    while (scanf("%d", &n) != EOF)
    {
        int i;

        for (i = 0; i < n; ++i)
            d[i] = 0;

        for (i = 1; i < n; ++i)
        {
            d[i - 1] += 1; d[i] -= 1;
            solve(i - 1, i);
            d[i - 1] -= 1; d[i] += 1;
        }
    }

    return 0;
}