Bracket combinations (Google Interview Question)

Write a function that prints all combinations of well-formed brackets. The input is a number which says how many pairs of brackets will the different outputs have. For Brackets(3) the output would be:
((()))  (()())  (())()  ()(())  ()()().

The solution below uses recursion. The logic here is very simple - every output is constructed starting with its first symbol. On each step a new symbol is added following these rules:

• rule 1: if the number of opened brackets is equal to the number of closing brackets, then the only next possible symbol to add is '('
• rule 2: if the number of opened brackets is more than the number of closing brackets, then there are two options - either we add ')' or '('
• rule 3: if the number of opened brackets is more than half the number of all brackets, then the construction went wrong and we break the whole case
• rule 4: if the number of opened brackets is less than the number of closing brackets, then the construction went wrong and we break the whole case
• rule 5: the last symbol of the output cannot be '('

private void Brackets(String output, int open, int close, int total) {
    if (output.length() == total * 2 && output.charAt(total * 2 - 1) != '(') {
        System.out.println(output);
    } else if (open > total || open < close) {
        return;
    } else {
        if ((open == close)) {
            Brackets(output + "(", open + 1, close, total);
        }
        if ((open > close)) {
            Brackets(output + "(", open + 1, close, total);
            Brackets(output + ")", open, close + 1, total);
        }
    }
}

public void Brackets(int total) {
    Brackets("", 0, 0, total);
}

This is an Interview Question for Software Engineers at Google. Here you can find more information.