【Leetcode 22】括号生成 —— 回溯法

22. 括号生成

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

示例 1：

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

示例 2：

输入：n = 1
输出：[“()”]

题目分析

解题思路：排列树，按节点遍历

1. 回溯结束条件：左括号数 = 右括号数 = 总数
2. 左括号数<总数， 字符串加入左括号
3. 右括号数<总数 且 左括号数>右括号数，字符串加入右括号

回溯法有“通用解题法”之称，用它可以系统地搜索问题的所有解。回溯法是一个既带有系统性又带有跳跃性的搜索算法。

更多案例可见 Leetcode 回溯法详解

List<String> res = new ArrayList<>();
public List<String> generateParenthesis(int n) {
    backtrack(n, 0, 0, "");
    return res;
}

void backtrack(int n, int l, int r, String str) {
    if (l == n && r == n) {
        res.add(str);
    }
    if (l < n) {
        backtrack(n, l + 1, r, str + "(");
    }
    if (r < n && l > r) {
        backtrack(n, l, r + 1, str + ")");
    }
}