LeetCode.022.Generate Parentheses 括号生成

题目描述

22 Generate Parentheses
https://leetcode-cn.com/problems/generate-parentheses/

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

---

解题过程

排列组合类题目，首先想到的就是 回溯法 backtracking，对于每个位置，可以选择 左括号 或者 右括号，但这个选择是有限制的，只有已选择的有多余要匹配的左括号才能选右括号。
用一个双端队列 deque 保存已选择的部分(用 StringBuilder 也可以)，变量 leftCount 记录已选择部分中左括号个数，当 deque 里左括号比右括号多时，可以选择右括号
结束条件：已经选择了 n 个左括号，则剩余一定全是右括号，直接补全右括号后加入结果集即可。当然，当 deque 中元素个数为 2n 时也结束。

时间复杂度很难分析，空间复杂度 O(n)

private static class SolutionV2020 {
    Set<String> res; // 最终结果集
    int n;
    public List<String> generateParenthesis(int n) {
        this.n = n;
        this.res = new HashSet<>();
        // n为1时特例处理
        if (n == 1) {
            List<String> trivial = new ArrayList<>();
            trivial.add("()");
            return trivial;
        }
        // 用一个双端队列 deque 保存已选择的部分
        Deque<String> deque = new LinkedList<>();
        deque.offer("("); // 第一个元素一定是左括号
        // 回溯生成括号
        backtrack(deque, 1);
        return new ArrayList<>(res);
    }

    // 回溯生成括号，deque 是当前已选择的部分， leftCount 是已选择部分中左括号个数
    private void backtrack(Deque<String> deque, int leftCount) {
        if (deque.size() == n * 2) {
            res.add(deque.stream().collect(Collectors.joining()));
            return;
        }
        // 已经选择了 n 个左括号，则剩余一定全是右括号
        if (leftCount == n) {
            String newParent = deque.stream().collect(Collectors.joining());
            for (int i = deque.size(); i < n * 2; i++) {
                newParent += ")";
            }
            res.add(newParent);
            return;
        }
        if (leftCount < n) {
            // 选择左括号
            deque.offer("(");
            backtrack(deque, leftCount + 1);
            // 回溯(撤回)
            deque.pollLast();

            // 当 deque 里左括号比右括号多时，可以选择右括号
            if (leftCount > deque.size() - leftCount) {
                // 选择右括号
                deque.offer(")");
                backtrack(deque, leftCount);
                // 回溯
                deque.pollLast();
            }
        }
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_022_GenerateParentheses.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_022_GenerateParentheses.java

---