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:

"((()))", "(()())", "(())()", "()(())", "()()()"

思路分析：这题很容易想到用DFS，转化成search问题求解，状态就是当前形成的括号字符串，目标是搜索出所有合法括号字符串。搜索树每一次分出两支，即后面加一个左括号或者右括号。但是实现的时候，需要注意维护两个counter，leftRemain和rightRemain用于维护目前剩余的带插入的左括号和右括号的个数，当leftRemain > rightRemain时，意味着剩余更多的左括号，这后面子树中是不可能有合法解的，因为右括号可以找左边已经添加的左括号匹配，而左括号只能和后面新添加的右括号匹配，这种情况需要减枝直接返回。当leftRemain <=rightRemain时，继续DFS。当leftRemain 和rightRemain都为0时，全部2*n个括号插入完毕，添加一个合法解。(注意这里不需要用栈做括号匹配判断是否合法，如果左括号等于右括号数目并且以左括号开头，那么必然合法，所有右括号都可以找到对应的左括号)

AC Code

public class Solution {
    
    public static List<String> res;
    
    public List<String> generateParenthesis(int n) {
        res = new ArrayList<String>();
        if(n <= 0) return res;
        dfs("", n, n);
        return res;
    }
    
    void  dfs(String state, int leftRemain, int rightRemain){
        if(leftRemain > rightRemain){
            return;
        }
        if(leftRemain == 0 && rightRemain == 0){
            res.add(state);
            return;
        } 
        if(leftRemain > 0){
            dfs(state + "(", leftRemain-1, rightRemain);
        } 
        if(rightRemain > 0){
            dfs(state + ")", leftRemain, rightRemain-1);
         }
    }
}

LeetCode Generate Parentheses