LeetCode-22. 括号生成

LeetCode-22. 括号生成

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

solution

动态规划

可以采用动态规划的思想，首先当n=1时，返回()，当n>1时，一定可以在n-1的基础上得到n的组合，即从第0项到第2*n-1项中插入()并放入vector中，但是要注意已经插入的不在重复插入

#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res, pre_vec, vec;
        if (n == 1) {
            res.push_back("()");
            return res;
        }
        pre_vec.push_back("()");
        while (--n) {
            for (int i = 0; i < pre_vec.size(); ++i) {
                string str = pre_vec[i];
                for (int j = 0; j < str.size(); ++j) {
                    string l_str, r_str, new_str;
                    l_str = str.substr(0, j);
                    r_str = str.substr(j, str.size());
                    new_str = l_str + "()" + r_str;
                    if (find(vec.begin(), vec.end(), new_str) == vec.end()) {
                        cout << new_str << endl;
                        vec.push_back(new_str);
                    }
                }
            }
            pre_vec = vec;
            cout << vec.size() << endl;
            res = vec;
            vec.clear();
        }
        return res;
    }
};
//leetcode submit region end(Prohibit modification and deletion)

int main() {
    Solution solution;
    solution.generateParenthesis(5);
}

回溯法

采用回溯法，当当前字符串的长度满足为2*n时，假如vector中，当左括号数小于n是添加左括号，当右括号数小于n时，添加右括号，由此就可以保证括号字符串一定合法

#include <vector>
#include <string>

using namespace std;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> res;
        string str;
        backtrack(res,str,0,0,n);
        return res;
    }

    void backtrack(vector<string> &res,string str,int l,int r,int n){
        if (str.size()==n*2){
            res.push_back(str);
        } else{
            if (l<n){
                backtrack(res,str+'(',l+1,r,n);
            }
            if (r<l){
                backtrack(res,str+")",l,r+1,n);
            }
        }
    }
};
//leetcode submit region end(Prohibit modification and deletion)

int main() {
    Solution solution;
    solution.generateParenthesis(5);
}