【力扣刷题】22. 括号生成

jayjay

发布于 2022-11-02 16:52:20

2800

发布于 2022-11-02 16:52:20

文章被收录于专栏：jay_blog

一、题目描述

来源:力扣（LeetCode）

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

示例 1：

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

示例 2：

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

提示：

1 <= n <= 8

二、思路分析

使用回溯法，分成3种情况:

当左右括号剩余数量一样多时，必定只能选择(，且后续不可能能选)，因为())是不合法的只能是()(，所以直接break，另外据此推论，在回溯过程中左括号数量一定小于等于右括号数量。
当左括号剩余数量大于0时且左右括号数量不等时，先选择左括号再选择右括号回溯（先右后左也可以）
当只有右括号时候，就直接选择，之后由于也没有其他选择直接break

三、代码实现

class Solution {
    private static final String[] parenthesis = {"(", ")"};
    public List<String> generateParenthesis(int n) {
        List<String> ans = new ArrayList<>();
        Map<String, Integer> parenthesisTimes = new HashMap<>();
        for (String ele: parenthesis) {
            parenthesisTimes.put(ele, n);
        }
        backtrack(ans, parenthesisTimes, new StringBuilder());
        return ans;
    }

    private void backtrack(List<String> ans, Map<String, Integer> remainParenthesis, StringBuilder sb) {
        if (remainParenthesis.get("(") == 0 &amp;&amp; remainParenthesis.get(")") == 0) {
            ans.add(sb.toString());
            return;
        }

        for (String ele: parenthesis) {
            if (remainParenthesis.get("(").intValue() == remainParenthesis.get(")").intValue()) {
                backtrackHelper(ans, sb, remainParenthesis, "(");
                break;
            } else if (remainParenthesis.get("(") > 0) {
                backtrackHelper(ans, sb, remainParenthesis, ele);
            } else {
                backtrackHelper(ans, sb, remainParenthesis, ")");
                break;
            }
        }
    }

    private void backtrackHelper(List<String> ans, StringBuilder sb, Map<String, Integer> remainParenthesis,
        String ele) {
        sb.append(ele);
        remainParenthesis.put(ele, remainParenthesis.get(ele) - 1);
        backtrack(ans, remainParenthesis, sb);
        sb.deleteCharAt(sb.length() - 1);
        remainParenthesis.put(ele, remainParenthesis.get(ele) + 1);
    }
}