22.括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

 

示例 1：

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]
示例 2：

输入：n = 1
输出：["()"]
 

提示：

1 <= n <= 8

题解1:递归+剪枝

import java.util.ArrayList;
import java.util.List;

/*
 * @lc app=leetcode.cn id=22 lang=java
 *
 * [22] 括号生成
 */

// @lc code=start
class Solution {
    public List<String> result;

    public List<String> generateParenthesis(int n) {
        // 递归+剪枝法
        // 时间复杂度:O(2^n)
        // 空间复杂度:O(1)
        result = new ArrayList<>();
        generate(0, 0, n, "");
        return result;
    }

    private void generate(int left, int right, int n, String s) {
        // recursion teminator
        if (left == n && right == n) {
            result.add(s);
            return;
        }
        // process current logic
        // drill down
        if (left < n) {
            // 左括号可以随时加，只要不超标
            generate(left + 1, right, n, s + "(");
        }
        if (left > right) {
            // 右括号必须必左括号少，才可加
            generate(left, right + 1, n, s + ")");
        }
        // restore state
    }
}