题目描述

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

示例：
输入：n = 3
输出：[“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

题目分析

如果从第几个括号的角度去分析，就太难了。
括号数量固定，则总字符数是固定的，因此可以从字符角度来做DFS。
使用 left 表示剩余的左括号数量，right 表示剩余的右括号数量。
在搜索的过程中可以做一些剪枝，将不符合符号规则的提前结束掉。

Java

private List<String> ans = new ArrayList<>();
private StringBuilder sb = new StringBuilder();

public List<String> generateParenthesis(int n) {
    dfs(n, n);
    return ans;
}

private void dfs(int left, int right) {
    if (left > right || left < 0) {
        return;
    }
    if (left == 0 && right == 0) {
        ans.add(sb.toString());
        return;
    }

    sb.append('(');
    dfs(left - 1, right);
    sb.deleteCharAt(sb.length() - 1);

    sb.append(')');
    dfs(left, right - 1);
    sb.deleteCharAt(sb.length() - 1);
}

Kotlin

private val ans = ArrayList<String>()
private val sb = StringBuilder()

fun generateParenthesis(n: Int): List<String> {
    dfs(n, n)
    return ans
}

private fun dfs(left: Int, right: Int) {
    if (left > right || left < 0) {
        return
    }

    if (left == 0 && right == 0) {
        ans.add(sb.toString())
        return
    }

    sb.append('(')
    dfs(left - 1, right)
    sb.deleteCharAt(sb.length - 1)

    sb.append(')')
    dfs(left, right - 1)
    sb.deleteCharAt(sb.length - 1)
}