括号问题

问题描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

“((()))”, “(()())”, “(())()”, “()()()”, “()(())”

数据范围：0<=n<=10

要求：空间复杂度O(n)，时间复杂度O(2^n)

示例

示例1

输入：1

返回值：[“()”]

示例2

输入：2

返回值：[“(())”，”()()”]

思路

相当于一共n个左括号和n个右括号，可以给我们使用，我们需要依次组装这些括号。每当我们使用一个左括号之后，就剩下n-1个左括号和n个右括号给我们使用，结果拼在使用的左括号之后就行了，因此后者就是一个子问题，可以使用递归：

• 终止条件：左右括号都使用了n个，将结果加入数组。
• 返回值：每一级向上一级返回后续组装后的字符串，即子问题中搭配出来的括号序列。
• 本级任务：每一级就是保证左括号还有剩余的情况下，使用一次左括号进入子问题，或者右括号还有剩余且右括号使用次数少于左括号的情况下使用一次右括号进入子问题。
• 注意：我们需要保证左括号出现的次数比右括号多时我们再使用右括号就一定能保证括号合法了，因此每次需要检查左括号和右括号的使用次数。

代码实现

```
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public void recursion(int left,int right,String temp,ArrayList<String> res,int n){
        //左右括号都用完了，就加入结果
        if(left==n&&right==n){
            res.add(temp);
            return;
        }
        //使用一次左括号
        if(left<n){
            recursion(left+1,right,temp + "（",res,n);
        }
        //使用一次有括号
        if(right<n&&right<left){
            recursion(left,right+1,temp + "）",res,n);
        }
    }
    public ArrayList<String> generateParenthesis (int n) {
        //记录结果
        ArrayList<String> res = new ArrayList<String>();
        //递归
        recursion(0,0,"",res,n);
        return res;
    }
}