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&lt;List&lt;String&gt;&gt; getBraceCombinations(int length) {
        if (length &lt;= 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&lt;List&lt;String&gt;&gt; paranthesesCombo = new ArrayList&lt;List&lt;String&gt;&gt;();
        generate(paranthesesCombo, new LinkedList&lt;String&gt;(), 0, 0, length/2);
        return paranthesesCombo;
    }

    private static void generate(List&lt;List&lt;String&gt;&gt; paranthesesCombo,  LinkedList&lt;String&gt; parenthesis, int openBrace, int closeBrace, int halfLength) {
        if (openBrace == halfLength &amp;&amp; closeBrace == halfLength) {
            paranthesesCombo.add(new ArrayList&lt;String&gt;(parenthesis));
        }
        if (openBrace &gt; halfLength || closeBrace &gt; openBrace) {
            return;
        }
        parenthesis.add("(");
        generate(paranthesesCombo, parenthesis, openBrace + 1, closeBrace, halfLength);
        parenthesis.removeLast();

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

    public static void main(String[] args) {
        List&lt;List&lt;String&gt;&gt; paths1 = Arrays.asList(
            Arrays.asList("(", ")")
        );
        assertEquals(paths1, getBraceCombinations(2));
        List&lt;List&lt;String&gt;&gt; paths = Arrays.asList(
                Arrays.asList("(", "(", ")", ")"),
                Arrays.asList("(", ")", "(", ")")
            );
        assertEquals(paths, getBraceCombinations(4));
    }
}
Jus a few minor points:


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.
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("...");
}

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&lt;String&gt; expectedPaths, 
        final int length) {
    final List&lt;List&lt;String&gt;&gt; braceCombinations = getBraceCombinations(length);

    final List&lt;String&gt; joinedBraceCombinations = 
        flattenBraceCombinations(braceCombinations);

    assertEquals(expectedPaths, joinedBraceCombinations);
}

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


With plain strings as expected output:

final List&lt;String&gt; expectedPaths = Arrays.asList(
    "((()))", 
    "(()())", 
    "(())()", 
    "()(())", 
    "()()()");
verifyPaths(expectedPaths, 6);

I would consider changing the current


List&lt;List&lt;String&gt;&gt;



return type to

Set&lt;List&lt;String&gt;&gt;


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