生成括号问题的解决思路

/*
* 生成括号
* 给定 n 对括号，请写一个函数以将其生成新的括号组合，并返回所有组合结果。
* 给定 n = 3, 可生成的组合如下:
* "((()))", "(()())", "(())()", "()(())", "()()()"
*
*
* 题目描述很简单，也很明白关键时解题思路
* 想一想这种生成括号的规则，其实隐含了一条信息：
* 那就是始终左括号的数量要大于或等于右括号的数量。也就是说，剩余的左括号的数
* 量要始终小于等于右括号。左括号只要有，就可以打印；而只有当剩余的右括号数量比左括号大时，才能打印右括号。
*
* 这个题目跟二叉树的路径遍历很像
*/

 private List GenerateParenthesis(int n)
 {
  List res=new List();
  string s = "";
  DFS(n,n,s,res);
  return res;
 }
 /// 

 /// 
 /// 
 /// 剩余左括号数量
 ///剩余右括号数量
 ///
 ///
 private void DFS(int left,int right,string s,List res)
 {
  //相当于二叉树节点为空，也就是深搜不能再深入了
  if (left == 0 && right == 0)
  {
res.Add(s);
return;
  }

  //相当于左节点存在
  if (left > 0)
  {
DFS(left-1,right,s+"(",res);
  }

  //相当于右节点存在
  if (right > left)
  {
DFS(left,right-1,s+")",res);
  }
 }

我们之前做过有效括号对的判断，跟这个比起来就是小儿科了。