22. 括号生成

难度中等1252收藏分享切换为英文关注反馈

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

示例：

1
2
3
4
5
6
7
8
输入：n = 3
输出：[
       "((()))",
       "(()())",
       "(())()",
       "()(())",
       "()()()"
     ]

通过次数166,462

提交次数218,996

一道经典的回溯算法的题目,lcnit表示左边括号的数目,rcnt表示右括号的数目;结束的条件是temp.size()==2*n,也就是满足长度;

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
26
27
28
29
30
31
32
33
class Solution {
public:
    vector<string>result;
    int maxn=0;

    void back_track(string temp,int lcnt,int rcnt){
        if(temp.size()==maxn*2){
            result.push_back(temp);
            return;
        }
        if(lcnt<maxn){
            temp.push_back('(');
            back_track(temp,lcnt+1,rcnt);
            temp.pop_back();
        }
        if(rcnt<lcnt){
            temp.push_back(')');
            back_track(temp,lcnt,rcnt+1);
            temp.pop_back();
        }
        return;
    }

    vector<string> generateParenthesis(int n) {
        string temp="";
        maxn=n;
        back_track(temp,0,0);
        return result;



    }
};