# Print all combinations of balanced parentheses

Given ( and ) and length of 4, generate the following combinations - ()() and (()).

Looking for code review, optimizations and best practices. Also verifying complexity to be O(2(n+1) - 1), where n is half the 'input length'.

public final class BraceCombinations {

private BraceCombinations() {}

/**
* Returns sets of valid combinations.
*
* @param length    the sum of length of all- opening + closing braces
* @return          the valid brace combinations
*/
public static List<List<String>> getBraceCombinations(int length) {
if (length <= 0) {
throw new IllegalArgumentException("The length should be greater than zero");
}

if (length % 2 == 1) {
throw new IllegalArgumentException("The length should be positive");
}

final List<List<String>> paranthesesCombo = new ArrayList<List<String>>();
generate(paranthesesCombo, new LinkedList<String>(), 0, 0, length/2);
return paranthesesCombo;
}

private static void generate(List<List<String>> paranthesesCombo,  LinkedList<String> parenthesis, int openBrace, int closeBrace, int halfLength) {
if (openBrace == halfLength && closeBrace == halfLength) {
}
if (openBrace > halfLength || closeBrace > openBrace) {
return;
}
generate(paranthesesCombo, parenthesis, openBrace + 1, closeBrace, halfLength);
parenthesis.removeLast();

generate(paranthesesCombo, parenthesis, openBrace, closeBrace + 1, halfLength);
parenthesis.removeLast();
}

public static void main(String[] args) {
List<List<String>> paths1 = Arrays.asList(
Arrays.asList("(", ")")
);
assertEquals(paths1, getBraceCombinations(2));
List<List<String>> paths = Arrays.asList(
Arrays.asList("(", "(", ")", ")"),
Arrays.asList("(", ")", "(", ")")
);
assertEquals(paths, getBraceCombinations(4));
}
}


Jus a few minor points:

1. I guess you have a typo here:

if (length % 2 == 1) {
throw new IllegalArgumentException("The length should be positive");
}


If length is 3 it prints that The length should be positive.

2. An exaplanatory variable would be a little bit easier to read here and it would express the purpose of the expression:

final boolean oddLength = (length % 2 == 1);
if (oddLength) {
throw new IllegalArgumentException("...");
}

3. It could be easier to read and modify the expected outputs in the tests, especially if length is higher than four:

Arrays.asList("(", "(", "(", ")", ")", ")"),


I'd rather use a custom verification method here:

private static void verifyPaths(final List<String> expectedPaths,
final int length) {
final List<List<String>> braceCombinations = getBraceCombinations(length);

final List<String> joinedBraceCombinations =
flattenBraceCombinations(braceCombinations);

assertEquals(expectedPaths, joinedBraceCombinations);
}

private static List<String> flattenBraceCombinations(
final List<List<String>> braceCombinations) {
final Joiner joiner = Joiner.on("");
final List<String> joinedBraceCombinations = new ArrayList<>();
for (final List<String> braceCombination: braceCombinations) {
final String joinedBraceCombination = joiner.join(braceCombination);
}
return joinedBraceCombinations;
}


With plain strings as expected output:

final List<String> expectedPaths = Arrays.asList(
"((()))",
"(()())",
"(())()",
"()(())",
"()()()");
verifyPaths(expectedPaths, 6);

4. I would consider changing the current

List<List<String>>


return type to

Set<List<String>>


The order of combinations doesn't look so important and it would make the test less specified (the order of expected paths would not be important too).