算法19(递归)-有效的括号

算法递归循环

发布时间 : 2020-07-04 16:34

字数:425 阅读 :

题目：
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:

[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]

一般看到这种比较具有对称性的一般都是可以采用递归思路进行求解的，主要是停止的状态是在什么地方，函数的参数设计，函数返回值以及涉及到里面递归调用的关系，一个小的子问题的理解，怎样理解这一个子问题是一个非常麻烦的事情，在这道题中，每一个()()()这种问题，都是()这种问题的的一个组合问题，在递归函数中，只需要找到函数的一个子解的终止条件，在这里，子解的终止条件就是当左括号和右括号都没有的时候，就可以进行返回操作，还有就是定义这个函数参数是(int left , int right,String item)分别表示，左右括号数量，每一次递归所加进来的字符串是哪种，具体的代码入下

 //用于存储的集合
  List<String> res = new ArrayList<>();
  public List<String> generateParenthesis(int n) {
    helper(n, n, "");
    return res;
  }
  private void helper(int left , int right , String curStr){
    if(left == 0 && right == 0 ) {
      res.add(curStr);
      return;
    }
    //1.结束条件，即没有左括号，也没有右括号，就返回，并将结果加入res
    //2.函数调用,还有左括号，就添加左括号
    if(left > 0) {
      helper( left - 1, right, curStr + "(" );
    }
    if(right > left) {
      helper(left, right - 1, curStr + ")" );
    }
  }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/generate-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1371769065@qq.com