LeetCode百题【括号生成】

题目描述

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

解法

回溯，深度优先搜索
如果左括号数量不大于 n，我们可以放一个左括号。
如果右括号数量小于左括号的数量，我们可以放一个右括号。

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> generateParenthesis(int n) {
        //1.定义结果集
        List <String> ans =new ArrayList<>();
        //2.调用函数后返回结果
        backtrack(ans, new StringBuffer(), 0, 0, n);
        return ans;
    }
    /**
     * 回溯算法
     * @param ans 结果集
     * @param cur 字符串缓冲区，存储括号结果
     * @param left 左括号的个数
     * @param right 右括号的个数
     * @param max  闭合括号的个数
     */
    public void backtrack(List<String> ans,StringBuffer cur,int left,int right,int max){
        //1.定义递归出口
        if(cur.length()==max*2){
            ans.add(cur.toString());
            return;
        }
        //2.当左括号个数小于总括号个数时，向其buffer添加左括号
        if(left<max){
            cur.append('(');
            //3.递归处理剩下的结果
            backtrack(ans, cur, left+1, right, max);
            //4.回溯返回后，减去回溯添加的括号
            cur.deleteCharAt(cur.length()-1);
        }
        //5.只要右括号个数小于左括号，就向buffer添加右括号。
        if (right<left){
            cur.append(')');
            //6.回溯处理剩下的结果
            backtrack(ans, cur, left, right+1, max);
            //7.回溯返回后，减去回溯添加的括号
            cur.deleteCharAt(cur.length()-1);
        }
    }
}