Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, givenn= 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

Solution

DFS - Only add valid parantheses

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList();
        backtrack(ans, "", 0, 0, n);
        return ans;
    }

    public void backtrack(List<String> ans, String cur, int open, int close, int max){
        if (cur.length() == max * 2) {
            ans.add(cur);
            return;
        }

        if (open < max)
            backtrack(ans, cur+"(", open+1, close, max);
        if (close < open)
            backtrack(ans, cur+")", open, close+1, max);
    }
}

Another implementation @lisali1203

public List<String> generateParenthesis(int n) {
    List<String> list = new ArrayList<String>();
    generateOneByOne("", list, n, n);
    return list;
}
public void generateOneByOne(String sublist, List<String> list, int left, int right){
    if(left > right){
        return;
    }
    if(left > 0){
        generateOneByOne( sublist + "(" , list, left-1, right);
    }
    if(right > 0){
        generateOneByOne( sublist + ")" , list, left, right-1);
    }
    if(left == 0 && right == 0){
        list.add(sublist);
        return;
    }
}

Or

public List<String> generateParenthesis(int n) 
{
    List<String> result = new LinkedList<String>();
    if (n > 0) generateParenthesisCore("", n, n, result); 
    return result;
}

private void generateParenthesisCore(String prefix, int left, int right, List<String> result)
{
    if (left == 0 && right == 0) result.add(prefix);
    // Has left Parenthesis    
    if (left > 0) generateParenthesisCore(prefix+'(', left-1, right, result);
    // has more right Parenthesis
    if (left < right) generateParenthesisCore(prefix+')', left, right-1, result);
}

Reference

https://leetcode.com/problems/generate-parentheses/solution/

Wikipedia: Catalan Number