暴力法：采用递归的方法罗列出所有的组合，然后进行判断
class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<String>();
        char[] current = new char[2*n];
        generateAll(current, 0, combinations);
        return combinations;
    }
    public void generateAll(char[] current, int pos, List<String> result){
        if(current.length == pos){
            System.out.println(current);
            if(valid(current)){
                result.add(new String(current));
            }
        }else{
            current[pos] = ‘(‘;
            generateAll(current, pos+1, result);
            current[pos] = ‘)‘;
            generateAll(current, pos+1, result);
        }
    }
    public boolean valid(char[] current){
        int balance = 0;
        for(int i = 0; i < current.length; i++){
            if(current[i] == ‘(‘){
                balance++;
            }else{
                balance--;
            }
            if(balance < 0) return false;
        }
        return (balance == 0);   
    }
}

回溯法：只有在我们知道序列仍然保持有效时才添加 ‘(‘ or ‘)‘，而不是像 方法一 那样每次添加。我们可以通过跟踪到目前为止放置的左括号和右括号的数目来做到这一点，
如果我们还剩一个位置，我们可以开始放一个左括号。 如果它不超过左括号的数量，我们可以放一个右括号。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        generateAll(result, "", 0, 0, n);
        return result;
    }
    public void generateAll(List<String> result, String ans, int open, int close, int max){
        if(close + open == 2*max){
            result.add(ans);
            return;
        }
        if(open < max)
            generateAll(result, ans + "(", open+1, close, max);
        if(close < open)
            generateAll(result, ans + ")", open, close+1, max);
    }
}