LeetCode-22. 括号生成

题目来源

22. 括号生成

题目详情

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

题解分析

解法一：递归回溯

1. 一看到题目中的“所有”等词语就要下意识的考虑能够使用回溯法来解决问题。
2. 本题中，同样可以使用回溯法来解决问题，只不过在回溯的时候需要注意几个问题。
   • 第一个问题就是括号的左右区间，左括号的数量一定需要大于右括号的数量。
   • 第二点就是，左右括号的数量相加一定等于2*n。
3. 具体地，对于dfs函数，可以使用两个参数：open和close来记录左右括号的数量，以此来判断边界。

class Solution {
    List ans = new ArrayList<>();
    int n;
    public List generateParenthesis(int n) {
        this.n = n;
        dfs(0, 0, "");
        return ans;
    }

    private void dfs(int open, int close, String res){
        if(open > n || close > open){
            return;
        }
        if(close + open == 2 * n){
            ans.add(res);
        }
        dfs(open + 1, close, res + "(");
        dfs(open, close + 1, res + ")");
    }
}

结果展示