地址 https://leetcode-cn.com/problems/generate-parentheses/
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。 示例 1: 输入:n = 3 输出:["((()))","(()())","(())()","()(())","()()()"] 示例 2: 输入:n = 1 输出:["()"] 提示: 1 <= n <= 8
解答
dfs 在可能的情况下 尝试填写( 与 )两种符号
填写(的情况比较宽松 只要当前该符号使用次数不为0即可
填写)的情况还需要额外观察填写的(个数 如果(个数比)个数少 则不能填写)
class Solution { public: vector<string> ans; stack<char> s; int limit = 0; int left = 0; int right = 0; void dfs(string& s, int idx) { if (idx == limit) { ans.push_back(s); return; } if(left > 0){ s += '('; left--; dfs(s, idx + 1); s.pop_back(); left++; } if (right > left && right>0) { s += ')'; right--; dfs(s, idx + 1); s.pop_back(); right++; } return; } vector<string> generateParenthesis(int n) { left = n; right = n; limit = 2 * n; string s; dfs(s,0); return ans; } };