Leet -- Generate Parentheses
题目描述
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
就是说给一个数字n，n对括号，打印出所有可能的组合。
思路：
1.每次分别追加左、右括号进行递归，n-1
2.完成能否添加左、右括号的判断
3.当n=1把当前的括号字符串添加到结果集中
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
就是说给一个数字n，n对括号，打印出所有可能的组合。
思路：
1.每次分别追加左、右括号进行递归，n-1
2.完成能否添加左、右括号的判断
3.当n=1把当前的括号字符串添加到结果集中
public class Solution {
private List<string> result = new List<string>();
private int total;
public IList<string> GenerateParenthesis(int n)
{
if (n <= 0){
return null;
}
total = n * 2;
Travel(total, "("); // always start with '('
return result;
}
private void Travel(int n, string str){
if(n == 1){
result.Add(str);
return ;
}
if(CanAppendLeft(str)){
Travel(n-1, str+"(");
}
if(CanAppendRight(str)){
Travel(n-1, str+")");
}
}
private bool CanAppendLeft(string str){
return str.Count(x=>x == '(') < total / 2;
}
private bool CanAppendRight(string str){
var leftCount = str.Count(x=>x == '(');
var rightCount = str.Count(x=>x == ')');
return leftCount > rightCount;
}
}