Description

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

For example, given n = 3, a solution set is:

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

Solution

DFS

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> parentheses = new ArrayList();
        if (n < 1) return parentheses;
        
        StringBuilder sb = new StringBuilder();
        generateParenthesis(n, n, sb, parentheses);
        return parentheses;
    }
    
    public void generateParenthesis(int left, int right, StringBuilder sb
                                    , List<String> parentheses) {
        if (left < 0 || right < 0 || left > right) {
            return;
        }
        
        if (left == 0 && right == 0) {
            parentheses.add(sb.toString());
            return;
        }
        
        sb.append('(');
        generateParenthesis(left - 1, right, sb, parentheses);
        sb.setCharAt(sb.length() - 1, ')');
        generateParenthesis(left, right - 1, sb, parentheses);
        sb.deleteCharAt(sb.length() - 1);
    }
}