((())) (()()) (())() ()(()) ()()().

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.