Leetcode22. 括号生成

题目描述

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

解题思路

算法描述

这道题考虑用暴力的方法，那么就是考虑DFS或者BFS两种方式。一般由于DFS的编码比较简单而选择DFS的方法。同时，在暴力的同时尽可能考虑剪枝。

首先一种最简单的暴力的方法就是将所有可能的括号序列列出来，然后写一个函数去判断这个序列是不是合理的。这种方法思路很简单，但是递归的时候有很多无用的路径，所以可以通过剪枝的方法优化一下，保证在加入(或者)后序列仍然有效的条件下才进行递归。

那么关键就在于如何保证加入括号后序列仍然保持有效。通过观察归纳，我们可以得出以下两个加入括号的条件：

• 左括号：在左括号的数量left小于给定的对数n的时候都可以加入左括号；
• 右括号：只有在右括号的数量right小于左括号数量left的时候才能加入右括号；

这样就可以写出DFS的代码。

参考代码

void DFS(vector<string>& ans, string& cur, int left, int right, int n){
    if(cur.size() == n * 2){
        ans.push_back(cur);
        return;
    }

    if(left < n){
        cur.push_back('(');
        DFS(ans,cur,left+1,right,n);
        cur.pop_back();
    }

    if(right < left){
        cur.push_back(')');
        DFS(ans,cur,left,right+1,n);
        cur.pop_back();
    }
}

vector<string> generateParenthesis(int n){
    vector<string>ans;
    string cur;
    DFS(ans,cur,0,0,n);
    return ans;
}

复杂度分析

这个的复杂度分析比较复杂，不要求掌握。

时间复杂度：$O(\frac{4^n}{\sqrt{n}})$​

空间复杂度：$O(n)$