leetcode|中等:22. 括号生成

1.题目

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

示例 1：

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

示例 2：

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

提示：

• 1 <= n <= 8

2. 题解

2.1 思路分析

思路1：DFS 比较简单 直接看代码

2.2 代码实现

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Solution {
    public void dfs(char[] brackets,int lNum,int rNum,int n,List<String> res){
        if(lNum==n && rNum==n) {
            res.add(new String(brackets));
            return;
        }

        // 增加左括号
        if(lNum<n){
            brackets[lNum+rNum] = '(';
            dfs(brackets,lNum+1,rNum,n,res);
        }
        // 增加右括号
        if(lNum>rNum&&rNum<n){
            brackets[lNum+rNum] = ')';
            dfs(brackets,lNum,rNum+1,n,res);
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        char[] brackets = new char[2*n];
        dfs(brackets,0,0,n,res);
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int in = 3;
        System.out.println(solution.generateParenthesis(in));
    }
}

2.3 提交结果

参考资料

1. https://leetcode-cn.com/problems/generate-parentheses/