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

括号生成

https://leetcode.cn/problems/generate-parentheses/description/

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

左括号数必须大于右括号数，且小于等于n
在这里插入图片描述

class Solution {
public:vector<string> ans;void generator(string ch, int n, int cur_l, int cul_r) {if (cur_l < cul_r) {return;}if (cur_l == n && cul_r == n) {// 结束条件是出现了三次(或者")"ans.push_back(ch);return;}if (cur_l <= n-1) {generator(ch + "(", n, cur_l + 1, cul_r);}if (cul_r <= n-1) {generator(ch + ")", n, cur_l, cul_r + 1);}return;}vector<string> generateParenthesis(int n) {generator("(", n, 1, 0);return ans;}
};

笨办法，迭代所有的节点，然后判断是否符合，
在这里插入图片描述

在这里插入图片描述

class Solution {
public:vector<string> ans;bool isValid(string ch) {stack<char> s;for (auto c : ch) {if (c == '(') {s.push(c);} else {if (!s.empty()) {s.pop();} else {return false;}}}if(s.empty()){return true;}return false;}void generator(string ch, int n, int cur) {if (cur == n*2) {// 结束条件是出现了三次(或者")"if (isValid(ch)){ans.push_back(ch);}return;}generator(ch+"(",n,cur+1);generator(ch+")",n,cur+1);return;}vector<string> generateParenthesis(int n) {generator("",n,0);return ans;}
};