LeetCode 精选 TOP 面试题（Java 实现）—— 括号生成

一、题目描述

1.1 题目

• 括号生成

• 给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：
[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

1.2 知识点

• 回溯算法

1.3 题目链接

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

二、解题思路

2.1 自研思路

  经典的回溯算法思想，通过以下条件来限制即可：

• 当左括号数量小于要求数量时添加左括号；
• 当右括号数量小于左括号数量时添加右括号；
• 截止条件为当左右括号数量相加等于要求数量时停止并输出结果即可；

三、实现代码

3.1 自研实现

class Solution {

    private List<String> list = new ArrayList<>(); 

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

    public void backtrack(int count1, int count2, int n, String str){
        if(count1 > n || count2 > n) return;
        if(count1 == n && count2 == n) list.add(str);
        if(count1 >= count2){
            backtrack(count1+1, count2, n, str+'(');
            backtrack(count1, count2+1, n, str+')');
        }

    }
}

3.2 示例代码

class Solution {
    public List<String> generateParenthesis(int n) {
        
        List<String> res = new ArrayList<>();
        if(n<=0) {
            return res;
        }
        dfs("", 0, 0, n, res);
        return res;
    }
    
    public void dfs(String s, int open, int close, int max, List<String> res) {
        if(s.length() == max*2) {
            res.add(s);
            return;
        }
        
        if(open < max) {
            dfs(s+"(", open+1, close, max, res);
        }
        if(close < open) {
            dfs(s+")", open, close+1, max, res);
        }
    }
}