AlgoPressAppearance
题目描述
https://leetcode.cn/problems/generate-parentheses
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
示例 1：
输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：
输入：n = 1
输出：["()"]
提示：
- 1 <= n <= 8
思路:根据剩余个数遍历【错误】
考虑n=1时，只能生成 () ，当 n=2 时，分别在左右添加。 代码有问题，不能包括所有情况。
参考代码
csharp
public class Solution {
public IList<string> GenerateParenthesis(int n) {
//递归
List<string> list = new List<string>();
if(n == 1){
list.Add("()");
}
else{
IList<string> result = GenerateParenthesis(n-1);
//把剩下的返回的结果拆分成两种加入到新的list里面去
for(int i=0; i<result.Count; i++){
string s1 = "()"+result[i];
string s2 = "("+result[i]+")";
string s3 = result[i]+"()";
list.Add(s1);
list.Add(s2);
if(s3 != s1){
list.Add(s3);
}
}
}
return list;
}
}
思路：回溯法
回溯生成括号，当剩余括号数量相等时，必须使用左括号，否则可以用左括号和右括号，当剩余数量为0时输出。
csharp
public class Solution{
private List<string> list = new List<string>();
private void dfs(string str, int n1, int n2){
if(n1 == 0 && n2 == 0){ //回溯到底，输出结果
list.Add(str);
return;
}
if(n1 == n2){ //左右括号数量相等的时候只能用左括号，说明括号都闭合了
dfs(str+"(",n1-1,n2);
}
else{ //可以使用左括号，也可以使用又括号
if(n1 > 0){
dfs(str+"(",n1-1,n2);
}
dfs(str+")",n1,n2-1);
}
}
public IList<string> GenerateParenthesis(int n){
dfs("",n,n);
return list;
}
}