Print all combinations of balanced parentheses

Question

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⁽ⁿ⁺¹⁾ - 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) {
            paranthesesCombo.add(new ArrayList<String>(parenthesis));
        }
        if (openBrace > halfLength || closeBrace > 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<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));
    }
}

Answer 1

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);
           joinedBraceCombinations.add(joinedBraceCombination);
       }
       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).