1.题目介绍
数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。
示例 1:
输入:n = 3
输出:["((()))","(()())","(())()","()(())","()()()"]
示例 2:
输入:n = 1
输出:["()"]
提示:
1 <= n <= 8
2.题解
2.1 暴力枚举
思路
我们利用递归枚举出n对括号(这里是n对,说明共有2n个括号)即共2^2n种情况,并在其中找到正确的括号匹配情况。
1.递归返回条件,一次次加入'('和')'后,最终字符串长度到达n之后,进行合法性检验,若正确,加入结果数组中
2.合法性检验,必须随时满足左边括号多于等于右边括号数量,最终两边括号数量必须相等。
3.递归过程,现将当前字符串加上'(',继续递归,后删除这个'(',再加上')'进行继续递归。
4.注意条件给的是n对,所以最开始填参数时,总数量应为2*n;
代码
class Solution {
private:
bool vaild(string &curr){
int balance = 0;
for(char ch:curr){
if (ch == '(') balance++;
else balance--;
if(balance < 0) return false;
}
return balance == 0;
}
void generateAll(vector<string> &ans, int n, string ¤t){
if(n == current.size()){
if(vaild(current)){
ans.push_back(current);
}
return;
}
current += '(';
generateAll(ans,n,current);
current.pop_back();
current += ')';
generateAll(ans,n,current);
current.pop_back();
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string current;
generateAll(ans, 2*n, current);
return ans;
}
};
复杂度分析
2.2 回溯法
思路
方法2.1有一个问题,就是当已经出现了不满足情况的括号组合,他依旧会继续递归下去,直到达到总括号数才会进行合法性检验,这样就浪费了很多递归资源
我们这里在每次递归中加入两个标记位置,分别标记已有的左括号数和有括号数目,左括号数目open < n(总共2n,左边的肯定要<n, =n的时候再加就超出了),有括号数目close < open < n即可。
这里所谓的回溯就是,在遇到不满足递归条件的中途节点,不会继续递归,而是回溯到上一级节点。这里就是使用if判断直接跳过本次递归过程,函数完成后自动回溯上一级调用节点。
代码
class Solution {
private:
void backtrack(vector<string> &ans, int n, int open, int close, string &curr){
if(n*2 == curr.size()){
ans.push_back(curr);
return;
}
if(open < n){
curr += '(';
backtrack(ans, n, open + 1, close, curr);
curr.pop_back();
}
if(close < open){
curr += ')';
backtrack(ans, n, open, close + 1, curr);
curr.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
string curr;
backtrack(ans, n, 0, 0, curr);
return ans;
}
};