括号生成
1. 题目
1.1. 描述
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且有效的括号组合。
1.2. 示例
示例 1
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]
示例 2
输入：n = 1
输出：[“()”]
1.3. 提示
1 <= n <= 8
1.4. 思路
- 回溯法。定义变量left和right分别表示剩余左右括号个数，递归遍历生成字符串
- 若生成的字符串中右括号个数大雨左括号个数，放弃这条线
- 若左右括号个数都为n时，则此时生成的字符串合法，存入结果
- 若左括号个数小于n时，则字符串中可以添加左括号继续递归
- 若右括号个数小于左括号时，则字符串中可以添加右括号继续递归
- 时间复杂度为O($2^n$)，空间复杂度为O($2^n$)
2. 代码
2.1. C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
dfs(0,0,ans,n,"");
return ans;
}
void dfs(int left,int right,vector<string> &ans,int n,string str){
if(left<right){ return; }
if(left==n&&right==n){
ans.push_back(str);
return;
}
if(left<n){
dfs(left+1,right,ans,n,str+"(");
}
if(left>right){
dfs(left,right+1,ans,n,str+")");
}
}
};
|
2.2. Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList<>();
dfs(0,0,ans,n,"");
return ans;
}
private void dfs(int left,int right,List<String> ans,int n,String str){
if(left<right){
return;
}
if(left==right&&left==n){
ans.add(str);
return;
}
if(left<n){
dfs(left+1,right,ans,n,str+"(");
}
if(left>right){
dfs(left,right+1,ans,n,str+")");
}
}
}
|