题目地址:https://leetcode-cn.com/problems/generate-parentheses/
题目描述
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
题目示例
示例:
输入:n = 3
输出:[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
解题思路
思路1:暴力解法。暴力求解思路其实很简单,简单穷举所有可能出现的结果2^(2n),然后删除不合格的匹配,即进行合法性检查即可。
思路2:递归求解。在递归求解过程中,根据题目需要注意递归四步曲,即递归终止条件、处理当前层、下探到下一层、清扫当前层的状态。在本题中,我们要注意的是左括号必须是先出现的,也就是说右括号必须在左括号之后出现,同时,因为n代表的是括号的对数,那么左括号和右括号必须出现n次,总结条件可知,递归终止条件为左括号left==n && right == n。当left<n时,递归添加左括号,下探下一层;当left>right&&right<n时,递归添加右括号,因为left是小于n的,所以只需要条件left>right即可,同时下探至下一层。
程序源码
class Solution { vector<string> res; public: vector<string> generateParenthesis(int n) { string s = ""; if(n == 0) return res; recur(0, 0, n, s); return res; } void recur(int left, int right, int n, string str) { //step1: terminator if(left == n && right == n) { res.push_back(str); return; } //step2: process //step3: drill down if(left < n) { recur(left + 1, right, n, str + "("); } if(left > right) //(left > right && right < n) { recur(left, right + 1, n, str + ")"); } //step4: reverse states } };