22. Generate Parentheses

Problem

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

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints:

• 1 <= n <= 8

Solution

此題要我們列出所有括弧的可能組合，因此我們可以用 backtracking 來解。雖然 backtracking 可以找出所有的組合，但是有些組合是不合法的。以下是一個合法的括弧組合。

讓我們來看一個不合法的括弧組合。一開始先放一個右括弧，這就使得接下來不管怎麼放，都不會得出一個合法的組合。依據這個例子，我們可以觀察出，當右括弧的剩餘數量大於或等於左括弧的剩餘數量時，我們就不可以放右括弧。

Backtracking

• Time:
• Space:

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> results = new ArrayList<>();
        dfs(n, n, new StringBuilder(), results);
        return results;
    }

    private void dfs(int left, int right, StringBuilder prefix, List<String> results) {
        if (left == 0 && right == 0) {
            results.add(prefix.toString());
        }

        if (left > 0) {
            prefix.append('(');
            dfs(left - 1, right, prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }

        if (right > left) {
            prefix.append(')');
            dfs(left, right - 1, prefix, results);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
}

參考

• 22. Generate Parentheses, LeetCode.
• 22. Generate Parentheses, LeetCode Solutions.