递归第一题（小白向）

本题用递归，可以说是dfs求解

（附上递归大部分模板）

本题括号匹配，要找出最多的，且合法的组合

按照 步骤

1. 找出递归终止条件 ： 当左右两边括号数都达到n时，结束递归
2. 不和法的状态：比如说 ）（）（）（肯定不合法，所以我们选择先放左括号，然后来匹配
3. 接下来看行后注释

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return string字符串ArrayList
     */

    public void recursion(int left,int right,String temp,ArrayList<String> res,int n){
        if (left == n && right == n){//终止条件
            res.add(temp);
            return;
        }

        if (left < n){//当左括号没用完时，递归
            recursion(left+1,right,temp+"(",res,n);
        }
        
        if (right<left && right < n){//先放左括号，保证左比右多，并且右括号没用完，递归
            recursion(left,right+1,temp+")",res,n);
        }
    }

    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        recursion(0,0,"",res,n);
        return res;
    }
}