Generate Parentheses

Question (LC.22)

The input n is a integer signifies the pairs of parentheses. Write a function that returns a list of all possible valid formation of n pairs of parentheses.

Example

I: n = -1
O: []
I: n = 0
O: [""]
I: n = 1
O: ["()"]
I: n = 2
O: ["(())", "()()"]
I: n = 3
O: ["((()))", "(())()", "()(())", "(()())", "()()()"]

Analysis

all possible => exhaustive search

Search

1. define subproblem
search by suffix (given a prefix, open, close) to find all valid formations
parenHelper(result, parens, int open, int close, int total)
2. recursive calls
if (open < total)
    parens.append('(')
    parenHelper(result, parens, open + 1, close, total)
    parens.deleteCharAt(parens.size() - 1)
if (close < open)
    parens.append(')')
    parenHelper(result, parens, open, close + 1, total)
    parens.deleteCharAt(parens.size() - 1)
3. base case
if (open == close)
    result.add(parens.toString())
    return;

Code

public List<String> generateParenthesis(int n) {
    List<String> result = new ArrayList<>();
    if (n < 0) return result;
    StringBuilder parens = new StringBuilder();
    parenHelper(result, parens, 0, 0, n);
    return result;
}

private void parenHelper(List<String> result, 
                         StringBuilder parens, 
                         int open, 
                         int close, 
                         int total) {
    if (open < total) {
        parens.append('(');
        parenHelper(result, parens, open + 1, close, total);
        parens.deleteCharAt(parens.length() - 1);
    }
    if (close < open) {
        parens.append(')');
        parenHelper(result, parens, open, close + 1, total);
        parens.deleteCharAt(parens.length() - 1);            
    }
    if (close == total) {
        result.add(parens.toString());
    }
}

Time & Space Complexity

Time O(2^n) Space O(2n)