LeetCode 22. Generate Parentheses

22. Generate Parentheses

Difficulty: medium

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

Only Version:

class Solution {
public:
    string str;
    int s;
    vector<string> ret;
    
    void search(int leftc, int unpairc) {
        if (leftc > this->s) {
            return ;
        }
        
        auto len = this->str.size();
        if (len == this->s * 2) {
            this->ret.push_back(str);
            return ;
        }
        
        // push left
        if (this->s - leftc > 0) {
            this->str.push_back('(');
            search(leftc + 1, unpairc + 1);
            this->str.pop_back();
        }
        
        // push right
        if (unpairc > 0) {
            this->str.push_back(')');
            search(leftc, unpairc - 1);
            this->str.pop_back();
        }
    }
    
    vector<string> generateParenthesis(int n) {
        this->s = n;
        this->search(0, 0);
        return this->ret;
    }
};

Rate:
Runtime: 4 ms, faster than 88.15% of C++ online submissions for Generate Parentheses.
Memory Usage: 14.3 MB, less than 80.99% of C++ online submissions for Generate Parentheses.

真是感慨了. 感动了自己.
19年安徽省赛原题, 当时放弃的一题, 如今没有查任何资料写出来了.
那些往年小事, 不值得一提了吧.

原题引用:
G. 括号序列
时间限制：2s
描述：
括号序列是指由 ‘(’ 和 ‘)’ 组成的序列，假如一个括号序列中，包含相同数量的左括号和右括号，并且对于每一个右括号，在他的左侧都有左括号和他匹配，则这个 括号序列就是一个合法括号序列，如（（ ））（ ）就是一个合法括号序列，但（（ ））（（ ）不是合法括号序列.

给出两个长度相同的合法括号序列 A 和 B , 那么 A < B 当且仅当:
● A 和 B 至少有一位不相同。
● 在 A 和 B 从左往右数第一个不相同的位置 i ， A[ i ] = ( , B[ i ] = )
比如A = （（ ））（）, B = （ ）（ ） （ ）， 则 A < B 。因为从左边数第一个不相同的是第二个字符，A[2] = ( , B[2] = )。对于长度 N，由于定义了小于关系，则可以通过这个关系推出所有长度为N的合法括号序列的大小关系，对于长度为6的合法括号序列，从小到大排列顺序如下:

1.（（（ ）））
2.（（）（））

1. （（ ））（ ）
2. （ ）（（ ））
3. （ ）（ ）（ ）
   给出 N 和 M， 求长度为 N 的合法括号序列中， 第 M 小的合法括号序列是？

输入
输入的第一行是 N 和 M(2 <= N <= 2000, 1 <= M <= 10^18)

输出
输出一个字符串，表示长度为 N 的平衡括号序列从小到大排列， 序号为 M 的字符串

样例输入

6 2
1

样例输出

（（）（））

————————————————
版权声明：本文为CSDN博主「zlzhucsdn」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_43581819/article/details/90405178