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

一、题目描述

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

示例 1：

输入：n = 3

输出：["((()))","(()())","(())()","()(())","()()()"]

示例 2：

输入：n = 1

输出：["()"]

提示：

• 1 <= n <= 8

二丶思路分析

回溯法

对于n对括号 ，会有 n个( 和 n个) 一共 2n 个字符

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

• 左括号数量不大于 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);
        }
    }
}

复杂度分析

• 时间复杂度：典型的卡特兰数问题，复杂度为
  网络异常，图片无法展示

  |
  n个左括号的个数。
• 空间复杂度：
  网络异常，图片无法展示

  |

运行结果

总结

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

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