NC26 括号生成

题目链接：https://www.nowcoder.com/practice/c9addb265cdf4cdd92c092c655d164ca

题目描述

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为："((()))", "(()())", "(())()", "()()()", "()(())"

数据范围：0≤n≤10

要求：空间复杂度 O(n)，时间复杂度 O(2^n)

示例 1：

输入：1
返回值：["()"]

示例 2：

输入：2
返回值：["(())","()()"]

解题代码

import java.util.*;


public class Solution {
    /**
     *
     * @param n int整型
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        //递归遍历
        recursion(0, 0, "", res, n);
        return res;
    }
    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 < n && left > right) {
            recursion(left, right + 1, temp + ")", res, n);
        }
    }
}