22. Generate Parentheses

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

回溯，记录左右括号的出现次数。
每次递归都添加左侧括号。
左侧括号的数量大于右侧括号时递归下一级才可以添加右侧括号。
当左侧括号和右侧括号达到n时，返回字符串。

class Solution {
    int N;
    List<String> ret;
    StringBuffer sb;
    
    public List<String> generateParenthesis(int n) {
        ret = new ArrayList<>();
        sb = new StringBuffer();
        N = n;
        backtracking(0, 0);
        return ret;
    }
    
    private void backtracking(int left, int right){
        if(left > N || right > N){
            return;
        }
        if(left == N && right == N){
            ret.add(sb.toString());
            return;
        }
        if(left > right){
            sb.append(')');
            backtracking(left, right+1);
            sb.delete(sb.length()-1, sb.length());        
        }
        sb.append('(');
        backtracking(left+1, right);
        sb.delete(sb.length()-1, sb.length());        
    }
}