leetcode-括号生成

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

思路

我们可以把一对括号看作一个整体，两个括号之前的组合只有两种放置的方式：

• 一个包含一个
• 两两互不包含

因此我们可以推出这个表达式：s = "(" + l + ")"+ r

代码

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        return *generate(n);
    }

    //记录n对括号的组合数
    shared_ptr < vector<string>> res[100] = {nullptr};

    shared_ptr<vector<string>> generate(int n) {
        if (res[n] != nullptr) return res[n];

        //为无括号的情况赋值
        if (n == 0) {
            res[0] = shared_ptr<vector<string>>(new vector<string>{""});
        }
        else {
            //创建一个临时数组，记录每次的组合
            auto temp = shared_ptr<vector<string>>(new vector<string>);
            for (int i = 0; i != n; ++i) {

                auto left = generate(i);
                auto right = generate(n - i - 1);

                for (const string& l : *left) {
                    for (const string& r : *right) {
                        temp->push_back("(" + l + ")" + r);
                    }
                }
                res[n] = temp;
            }
        }
        return res[n];
    }
};

复杂度

略。。