LeetCode 22. 括号生成

题目

22. 括号生成

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

示例 1：

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

示例 2：

输入：n = 1
输出：[“()”]

提示：

• 1 <= n <= 8

思路

算法：
dfs算法 O(n * 2²ⁿ)

n 对括号一共有 2n 个位置，2n 个位置任意放左括号或者右括号有 2²ⁿ 种可能。
用二进制数表示每一种情况，某一位为 1 表示放左括号，为 0 表示放右括号，对每一种情况进行分析是否为合法的括号序列。

复杂度：时间复杂度为 O(n * 2²ⁿ) ,空间复杂度为 O(2²ⁿ)

代码

C++代码：

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ans;
        int i,m=1<<(2*n),j,d=2*n;
        for(i=0;i<m;i++){
            int t=0,l=0,r=0;
            string s="";
            bool f=true;
            for(j=0;j<d;j++){
                if(i>>j&1){
                    t++;
                    l++;
                    s+='(';
                }else{
                    r++;
                    s+=')';
                }
                if(r>l) f=false;
            }
            if(t!=n||!f) continue;
            ans.push_back(s);
        }
        return ans;
    }
};

python3代码：

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        res = []
        self.dfs(n, n, "", res)
        return res

    def dfs(self, l, r, path, res):
        if l == r == 0:
            res.append(path)
            return
        if l > r or l < 0 or r < 0:
            return
        self.dfs(l - 1, r, path + "(", res)
        self.dfs(l, r - 1, path + ")", res)