Leetcode22. 括号生成

题目描述

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

示例 1：

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

示例 2：

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

提示：

  • 1 <= n <= 8

解题思路

算法描述

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

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

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

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

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

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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(4nn)O(\frac{4^n}{\sqrt{n}})​

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