Finding all combinations of well-formed brackets


Question

This came up while talking to a friend and I thought I'd ask here since it's an interesting problem and would like to see other people's solutions.

The task is to write a function Brackets(int n) that prints all combinations of well-formed brackets from 1...n. For Brackets(3) the output would be

()
(())  ()()   
((()))  (()())  (())()  ()(())  ()()()
1
32
2/1/2017 12:23:26 AM

Accepted Answer

Took a crack at it.. C# also.

public void Brackets(int n) {
    for (int i = 1; i <= n; i++) {
        Brackets("", 0, 0, i);
    }
}

private void Brackets(string output, int open, int close, int pairs) {
    if((open==pairs)&&(close==pairs)) {
        Console.WriteLine(output);
    } else {
        if(open<pairs)
            Brackets(output + "(", open+1, close, pairs);
        if(close<open)
            Brackets(output + ")", open, close+1, pairs);
    }
}

The recursion is taking advantage of the fact that you can never add more opening brackets than the desired number of pairs, and you can never add more closing brackets than opening brackets..

50
3/16/2016 12:18:06 PM

The number of possible combinations is the Catalan number of N pairs C(n).

This problem was discussed on the joelonsoftware.com forums pretty exentsively including iterative, recursive and iterative/bitshifting solutions. Some pretty cool stuff there.

Here is a quick recursive solution suggested on the forums in C#:

C#

public void Brackets(int pairs) {
    if (pairs > 1) Brackets(pairs - 1);
    char[] output = new char[2 * pairs];

    output[0] = '(';
    output[1] = ')';

    foo(output, 1, pairs - 1, pairs, pairs);
    Console.writeLine();
}

public void foo(char[] output, int index, int open, int close,
        int pairs) {
    int i;

    if (index == 2 * pairs) {
        for (i = 0; i < 2 * pairs; i++)
            Console.write(output[i]);
        Console.write('\n');
        return;
    }

    if (open != 0) {
        output[index] = '(';
        foo(output, index + 1, open - 1, close, pairs);
    }

    if ((close != 0) && (pairs - close + 1 <= pairs - open)) {
        output[index] = ')';
        foo(output, index + 1, open, close - 1, pairs);
    }

    return;
}

Brackets(3);

Output:
()
(()) ()()
((())) (()()) (())() ()(()) ()()()


Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Icon