描述

难度：中等

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

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

思路

方法一：回溯法

和全排列一样的思想，先一步一步把末端的数填满，然后再返回上一层，继续填。

在这里也是一样的思路，在这个List里面，只要它是有效的，就继续往List里面添加 ( or )

再来看一个规则：

假如 n=3，那么( 只能有3个，)也只能有3个，失衡了就不是有效括号了。

再想一下，如果左括号( 数量小于 n ，那么我们就可以把它放进list里面；如果右括号 )小于左括号( 数量，那我们可以放一个右括号，这样才能组成有效括号。

题解

这个回溯挺有意思的，可以debug一步一步来看看。

public class 括号生成22 {
    public static void main(String[] args) {
        /*
        放括号成为有效括号的原则：
        如果 左括号 ( 数量 小于 n ，那么需要放一个，且优先级要比下面这个判断要高
        如果 右括号 ) 数量 小于 左括号) 数量，那么需要放一个
        */
        System.out.println(generateParenthesis(3));
    }

    static List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(n, 0, 0, res, new StringBuilder());
        return res;
    }
	//空间复杂度：O(n)
    static void backtrack(int n, int open, int close, List<String> res, StringBuilder track) {
        if (track.length() == n * 2) {
            res.add(track.toString());
            return;
        }
        if (open < n) {
            track.append("(");
            backtrack(n, open + 1, close, res, track);
            track.deleteCharAt(track.length() - 1);
        }
        if (close < open) {
            track.append(")");
            backtrack(n, open, close + 1, res, track);
            track.deleteCharAt(track.length() - 1);
        }
    }
}