LeetCode-使用递归解决括号生成问题

问题可见：https://leetcode.com/problems/generate-parentheses/

描述

给定n对括号，编写一个函数来生成格式正确的括号的所有组合。

例如，给定n = 3，解集是：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路：

意题的英文给你n值，让你找到所有格式正确的圆括号匹配组，中题目给出已经了n = 3的所有查询查询结果。遇到这种问题，第一直觉就是用到递归或者堆栈，我们选取递归来解决，也就是helper函数的功能，从参数上来看肯定很好理解了，leftRest代表还有几个左括号可以用，rightNeed代表还需要几个右括号才能匹配，初始状态当然是rightNeed = 0, leftRest = n，递归的终止状态就是rightNeed == 0 && leftRest == 0，也就是左右括号都已匹配完毕，把然后str加入到链表中即可。

import java.util.ArrayList;
import java.util.List;
//初始先有(,)是根据(的添加之后才产生的
//终止条件为(和)均为空
public class getList {
    List<String> list = new ArrayList<>();
    public List<String> generateParenthesis(int n) {
        helper(list,"",n,0);
        return list;
    }

    public void helper(List<String> list, String str, int LeftRest,int RightNeed){
        //终止条件
        if(LeftRest==0&&RightNeed==0){
            list.add(str);
            return;
        }
       if(RightNeed>0) {
           helper(list, str + ")", LeftRest, RightNeed - 1);
       }
       if(LeftRest>0) {
           helper(list, str + "(", LeftRest - 1, RightNeed + 1);
       }
    }
	//test
    public static void main(String[] args) {
        System.out.println(new getList().generateParenthesis(3));
    }
}