【递归 &回溯】LeetCode-22. 括号生成

22. 括号生成。

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

算法分析

解题思路
满足有效括号序列的性质

• 1、前缀序列中左括号的数量>=右括号的数量
• 2、左括号的数量=右括号的数量
  DFS
• 1、dfs(int n,int l,int r,String s)：n表示最多有n个左括号和右括号，l表示左括号的个数，r表示- 右括号的个数，s表示当前的序列
• 2、若l < n，左括号的个数小于n，则可以在当前序列后面拼接左括号
• 3、若r < l，右括号的个数小于左括号的个数，则可以在当前序列后面拼接右括号

class Solution {
    List<String> ans = new ArrayList<>();

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

    private void dfs(int n, int lc, int rc, String path) {
        if (lc == n && rc == n) ans.add(path);
        if (lc < n) dfs(n, lc + 1, rc, path + "(");
        if (rc < lc) dfs(n, lc, rc + 1, path + ")");
    }
}

复杂性分析

时间复杂度：O(Cn/2n)
空间复杂度：O(m + n)