#yyds干货盘点# 面试必刷TOP101：括号生成

1.简述：

描述

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

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

"((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：

要求：空间复杂度 ，时间复杂度 

示例1

输入：

1

返回值：

["()"]

示例2

输入：

2

返回值：

["(())","()()"]

2.代码实现：

import java.util.*;
public class Solution {
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 && left > right){
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;
}
}