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

() (())  ()()    ((()))  (()())  (())()  ()(())  ()()() 

Answer 1

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..

Answer 2

Python version of the first voted answer.

def foo(output, open, close, pairs):     if open == pairs and close == pairs:         print output     else:         if open<pairs:             foo(output+'(', open+1, close, pairs)         if close<open:             foo(output+')', open, close+1, pairs)  foo('', 0, 0, 3)