22. 括号生成

22. 括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路：
1.暴力法：排列组合将所有的情况列出，判断出有效的括号组合
2.回溯法：添加右括号要满足两个条件
插入数量不超过n
可以插入 ）右括号 的前提是 (左括号 的数量大于 ）右括号

class Solution {
    public List<String> generateParenthesis(int n) {
        //括号组合
        List<String> combinations = new ArrayList<String>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    public void generateAll(char[] current, int pos, List<String> result){
        if(pos == current.length){
            //是否符合有效组合
            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(char c : current){
            if(c == '('){
                ++balance;
            }else{
                --balance;
            }
            if(balance < 0){
                return false;
            }
        }
        return balance == 0;
    }
}