Interview Question for Software Engineer at Google:

public class Parenth2 {

    static int total = 3;

    static private void Brackets(String output, int open, int close, int pairs) {
        if ((open == pairs) && (close == pairs) && output.length() == total * 2) {
            System.out.println(output);
        } else {
            if (open < pairs)
                Brackets(output + "(", open + 1, close, pairs);
            if (close < open)
                Brackets(output + ")", open, close + 1, pairs);
        }

    }

    public static void main(String[] args) {
        Brackets("", 0, 0, total);
}
}

You almost got thte answer, just a couple of errors...
/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

/**
 *
 * @author Owner
 */
public class Parenth4 {

    static private void Brackets(String output, int open, int close, int pairs, boolean opened, boolean closed, int total) {
        if ((open == pairs) && (close == pairs) && output.length() == total * 2) {
            System.out.println(output);
        } else {
            if ((open < pairs))
                Brackets(output + "(", open + 1, close, pairs,true, closed, total);
            if ((close < open)&& opened)
                Brackets(output + ")", open, close + 1, pairs,opened,closed, total);
        }

    }

    public static void Brackets(int total) {
        Brackets("", 0, 0, total,false,false, total);
    }
    public static void main(int number){
        Brackets(number);
    }
}

This is a DP/memoization question, I believe. The base case is 0 and 1 bracket (the answer is empty or (). The recurrence is:

bracket(n) =
all combination of results from bracket(n-1) and from bracket (1)
from bracket(n-2) and bracket(2)
.
.
from bracket(1) and bracket(n-1)
lastly, '(' . bracket(n-1) ')'

The DP version of the above recurrence is straightforward. (Btw, this recurrence obviously will produce duplicate, but it's not hard to produce a modification that does not produce duplicate.) ;)

Here is a F# implementation:

let rec Br total output openp closep =
    if openp = total && closep = total
    then
            printfn "%s" output
    else
            if openp < total then Br total (output + "( ") (openp + 1) closep
            if closep < openp then Br total (output + " )") openp (closep + 1)

let Brackets total =
    Br total "" 0 0

Brackets 5

let read = System.Console.ReadLine()

void parens(int nPairs) {
        parens("", nPairs, nPairs);
    }

    void parens(string ans, int leftCount, int rightCount) {
        if (leftCount==0 && rightCount==0) {
          cout << ans << endl;
          return;
        }
        if (leftCount>0) {
          parens(ans+"(", leftCount-1, rightCount);
        }
        if (rightCount>leftCount) {
          parens(ans+")", leftCount, rightCount-1);
        }
    }

To Remove duplicates simply use java Set :)

public static String bracket(int a) {

        Set s = new TreeSet();
        bracketIntern(s, a, "", "");
        System.out.println(s);
        return s.toString();
    }

    public static void bracketIntern(Set set,int a, String preFix,String suffix) {
        if(a == 1) {
            set.add(preFix+"()"+suffix);
            return;
        }
        bracketIntern(set, a-1, preFix+"()", suffix);
        bracketIntern(set, a-1, preFix+"(", ")"+suffix);
        bracketIntern(set, a-1, preFix, "()"+suffix);
    }

I think you can also build a trie, and the traverse the trie to print out all the combinations.

Complete python program to print the all combinations of well-formed brackets.

How to calculate its Big-o?
The recursive recurrence seems a little bit complicated.

----
def brackets(n):
    sol = []
    li = [' ' for x in range(n*2)]
    def recu_brackets(opened, closed):
        if n - opened:
            li[opened + closed] = '('
            recu_brackets(opened + 1, closed)
        if n - closed and opened > closed:
            li[opened + closed] = ')'
            recu_brackets(opened, closed + 1)
        if opened == n and closed == n:
            sol.append(''.join(li))
    recu_brackets(0, 0)
    print ' '.join(sol)

brackets(3)

wasn't all that neat. o well

public class MakeBrackets{
    static List<String> make(int number){
        List<String> list = new LinkedList<String>();

        if (number == 0) {list.add(""); return list;}
        if (number == 1) {list.add("()"); return list;}

        for (int i = 0; i < number; i++){
            for (String item : make(i)){
                for (String item2 : make(number - 1 - i)){
                    list.add("(" + item + ")" + item2);
                }
            }
        }
        return list;
    }

    public static void main(String[] args){
        System.out.println(make(Integer.parseInt(args[0])));
    }
}