Leetcode22: 括号生成(递归)

方法1：暴力解法

　　难点：

　　　　递归的生成所有的括号（递归算法）

　　　　　　generateAll(current, 0, combinations)　　current:当前字符数组， pos:当前写入括号的位置， combinations:当前所有合法的长度为2n的集合

　　　　判断括号是否合法

　　　　　　遍历字符数组，遇到'(', i++, 遇到‘)’, i--; 如果括号合法，i应该是0

class Solution {
    public List generateParenthesis(int n) {
        List combinations = new ArrayList();//存放合法括号的集合
        char[] current = new char[2*n]; //存放当前括号字符数组
        generateAll(current, 0, combinations);//递归函数
        return combinations;
    }

    //递归函数
    public void generateAll(char[] current, int position, List result){
        //递归出口
        if(current.length == position){//如果当前长度达到2*n，则出递归
            if(valid(current)){
                result.add(new String(current));
            }
        }else{
            current[position] = '(';
            generateAll(current, position+1,result);
            current[position] = ')';
            generateAll(current,position+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;
    }

}

方法2：暴力解法改进

方法1在生成长度为2*n的字符串后再判断这个字符串是否合法，显然，过程中生成了很多不合法的字符串

改进：在生成字符串的时候就考虑只允许生成合法的字符串（

　　　　若'('的数量小于n，则当前位置可以填‘（’

　　　　若')'的数量小于'('，则当前位置可以填’）‘

　　　　注意每次填完括号后要把当前位置还原

class Solution {
    public List generateParenthesis(int n) {
        List result = new ArrayList();
        generateAll(new StringBuilder(),result,0,0,n);
        return result;
    }

    public void generateAll(StringBuilder cur, List result, int left, int right, int pos){
        //递归出口
        if(cur.length() == pos*2){
            result.add(cur.toString());
            return;
        }else {
            if(left//左括号共n个，如果当前还有左括号剩余
                cur.append('(');
                generateAll(cur,result,left+1,right,pos);
                cur.deleteCharAt(cur.length()-1);//还原，以备当前位置添加右括号的情况
            }
            if(right < left){
                cur.append(')');
                generateAll(cur,result,left,right+1,pos);
                cur.deleteCharAt(cur.length()-1);
            }
        }
    }
}