All Balanced Parentheses in Java

The challenge

Write a function that makes a list of strings representing all of the ways you can balance n pairs of parentheses

Examples

balancedParens(0) returns ArrayList<String> with element:  ""
balancedParens(1) returns ArrayList<String> with element:  "()"
balancedParens(2) returns ArrayList<String> with elements: "()()","(())"
balancedParens(3) returns ArrayList<String> with elements: "()()()","(())()","()(())","(()())","((()))"

The solution in Java code

Option 1:

import java.util.ArrayList;

public class BalancedParens {

    public static ArrayList <String> balancedParens (int n) {
        ArrayList<String> lst = new ArrayList<>();
        StringBuilder sb = new StringBuilder();
        dfs(sb,lst,0,0,n);
        return lst;
    }
    
    private static void dfs(StringBuilder sb, ArrayList<String> lst, int open, int close, int max) {
        if (close==max) {
            lst.add(sb.toString());
            return;
        }
        if (open>close)  {
            sb.append(')');
            dfs(sb,lst,open,close+1,max);
            sb.deleteCharAt(sb.length()-1);
        }
        if (open<max) {
            sb.append('(');
            dfs(sb,lst,open+1,close,max);
            sb.deleteCharAt(sb.length()-1);
        }
    }
}

Option 2:

import java.util.ArrayList;
import java.util.List;

public class BalancedParens {
  
  public static List<String> balancedParens (int n) {
    List<String> result = new ArrayList<>(n);
    balancedParens("", n, 0, 0, result);
    return result;
  }
  
  private static void balancedParens(String str, int n, int numOpens, int numCloses, List<String> list) {
    if(numCloses == n) {
      list.add(str);
      return;
    }
    if(numOpens < n) {
      balancedParens(str + "(", n, numOpens + 1, numCloses, list);
    }
    if(numOpens > 0 && numCloses < numOpens) {
      balancedParens(str + ")", n, numOpens, numCloses + 1, list);
    }
  }
}

Option 3:

import java.util.*;

public class BalancedParens {
    public static List<String> balancedParens(int n) {
        List<List<String>> sequence = new ArrayList<>(n + 1);
        sequence.add(Collections.singletonList(""));
        for (int i = 1; i <= n; i++) {
            List<String> currentList = new ArrayList<>();
            for (int j = 0; j < i; j++) {
                List<String> leftList = sequence.get(j);
                List<String> rightList = sequence.get(i - 1 - j);
                for (String inner : leftList) {
                    String braced = '(' + inner + ')';
                    for (String outer : rightList)
                        currentList.add(braced + outer);
                }
            }
            sequence.add(currentList);
        }
        return sequence.get(n);
    }
}

Test cases to validate our solution

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.*;

public class SolutionTest {
   @Test
   public void testExample() {
      List<String> warriorsList = new ArrayList<String>();
      //test for n = 0
      warriorsList = BalancedParens.balancedParens(0);
      assertEquals(new ArrayList<String>(Arrays.asList(new String[] {""}))
                   ,  warriorsList
                   );
    //test for n = 1
      warriorsList = BalancedParens.balancedParens(1);
      assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"()"}))
                   , warriorsList
                   );
    //test for n =2
      warriorsList = BalancedParens.balancedParens(2);
      Collections.sort(warriorsList);
      assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"(())","()()"}))
                   , warriorsList
                   );
    //test for n = 3
      warriorsList = BalancedParens.balancedParens(3);
      Collections.sort(warriorsList);
      assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"((()))","(()())","(())()","()(())","()()()"}))
                   , warriorsList
                   );
    //test for n = 4
      warriorsList = BalancedParens.balancedParens(4);
      Collections.sort(warriorsList);
      assertEquals(new ArrayList<String>(Arrays.asList(new String[] {"(((())))","((()()))","((())())","((()))()","(()(()))","(()()())","(()())()","(())(())","(())()()","()((()))","()(()())","()(())()","()()(())","()()()()"}))
                  , warriorsList
                  );
    
    }
}