【刷题记录】22. 括号生成

一、题目描述

来源：

力扣（LeetCode）

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

有效的

 括号组合。

示例 1：

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


示例 2：

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


提示：

• 1 <= n <= 8

二丶思路分析

回溯法

对于

n

对括号 ，会有 

n

个

(

 和 

n

个

)

 一共 

2n

 个字符

我们使用DFS来递归生产所有的序列情况，为了减少递归的次数，每次递归时候

• 左括号数量不大于&nbsp;
  n
  ，我们可以放一个左括号。

• 如果右括号数量小于左括号的数量，我们就放一个右括号。来保证我们的括号是成对而且有效的。

三、代码实现

class Solution {
 public List<String> generateParenthesis(int n) {
 List<String> res = new ArrayList<String>();
 dfs(res, new StringBuilder(), 0, 0, n);
 return res;
 }

 public void dfs(List<String> ans, StringBuilder cur, int l, int r, int len) {
 if (cur.length() == len * 2) {
 ans.add(cur.toString());
 return;
 }
 if (l < len) {
 cur.append('(');
 dfs(ans, cur, l + 1, r, len);
 cur.deleteCharAt(cur.length() - 1);
 }
 if (r < l) {
 cur.append(')');
 dfs(ans, cur, l, r + 1, len);
 cur.deleteCharAt(cur.length() - 1);
 }
 }
}


复杂度分析

• 时间复杂度：典型的卡特兰数问题，复杂度为&nbsp;
  
  
   
  n
  个左括号的个数。

• 空间复杂度：
  
  

运行结果

总结

这道题就是遍历所有n对括号组合生成的字符串，然后做有效括号的验证。

但是这些会产生比较多不符合的。所以我们可以根据规律，进一步的缩小范围，让它只递归产生我们需要的结果。