4.括号生成

4.1题目

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

• 示例一：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

• 示例二：

输入：n = 1
输出：["()"]

4.2解法：回溯

• 此解法当n>=8时，超出时间限制

4.2.1回溯思路

（1）函数返回值以及参数

private void backing(int startIndex,int n)

（2）终止条件

if(sb.length() == 2*n){
    //判断当前路径是否为有效括号
    if(isValid(sb)){
    	res.add(new String(sb.toString()));
    }
    return;
}

（3）遍历过程

for(int i=startIndex;i<2*n;i++){
	sb.append('(');
    backing(i+1,n);
     
    sb.deleteCharAt(sb.length()-1);

    if(i!=0){
		sb.append(')');
        backing(i+1,n);
		sb.deleteCharAt(sb.length()-1);
    }
}

• 验证是否为回文串方法

	public boolean isValid(StringBuffer sb){

        Deque<Character> deque=new LinkedList<>();
        for(int i=0;i<sb.length() ;i++){
            if(sb.charAt(i)=='('){
                //左括号
                deque.push('(');
            }else if( !deque.isEmpty() && deque.peek()=='(' ){
                deque.pop();
            }else{
                return false;
            }
        }
        return deque.isEmpty();
    }

4.2.2代码

	List<String> res=new ArrayList<>();
    StringBuffer sb=new StringBuffer();

    public List<String> generateParenthesis(int n) {
        backing(0,n);
        return res;
    }

    private void backing(int startIndex,int n){
        if(sb.length() == 2*n){
            //判断当前路径是否为有效括号
            if(isValid(sb)){
                res.add(new String(sb.toString()));
            }
            return;
        }

        for(int i=startIndex;i<2*n;i++){
            sb.append('(');
            backing(i+1,n);
            sb.deleteCharAt(sb.length()-1);

            if(i!=0){
                sb.append(')');
                backing(i+1,n);
                sb.deleteCharAt(sb.length()-1);
            }
        }
    }

    public boolean isValid(StringBuffer sb){

        Deque<Character> deque=new LinkedList<>();
        for(int i=0;i<sb.length() ;i++){
            if(sb.charAt(i)=='('){
                //左括号
                deque.push('(');
            }else if( !deque.isEmpty() && deque.peek()=='(' ){
                deque.pop();
            }else{
                return false;
            }
        }
        return deque.isEmpty();
    }