22. Generate Parentheses Medium

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: ["()"]

Approach

Input: An integer n, representing the number of pairs of parentheses to generate.

Output: Return all possible and valid parentheses combinations.

This problem belongs to Subset Enumeration problems.

Three Questions of Backtracking

1. Current Operation?

   • At the current position i (representing the length of currently constructed parentheses):
     • If the number of left parentheses ( denoted by open_count hasn't reached n, we can place a left parenthesis.
     • If the number of right parentheses ) (which is i - open_count) is strictly less than the number of left parentheses open_count, we can place a right parenthesis to guarantee validity.
   • At each step, try a valid choice and put the current selection into path.

2. Sub-problem?

   • After placing a parenthesis, recursively handle the next position (i+1), and update the count of left parentheses (for () or right parentheses (indirectly computed by i - open_count).
   • Continue placing remaining parentheses until the entire parenthesis string is constructed.

3. Next Sub-problem?

   • When the current position i attempts placing ( or ), it forms a binary branching.
   • Continue recursing until the path length equals 2 * n, forming a valid combination which is then appended to the results list ans.

Pruning Conditions

• If the number of left parentheses exceeds n, prune directly (invalid).
• If the number of right parentheses exceeds the number of left parentheses, prune directly (invalid).

Implementation

python

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []  # Used to store all valid parentheses combinations
        path = []  # Used to store the construction path of the current parentheses combination

        def dfs(i: int, open_count: int):
            """
            i: explicitly current character position being processed
            open_count: currently used count of left parentheses
            """
            if i == 2 * n:
                # When the constructed parentheses length reaches 2 * n, a valid combination is found
                ans.append(''.join(path))
                return
            
            # 1. Choose left parenthesis
            if open_count < n:
                path.append('(')
                dfs(i + 1, open_count + 1)
                path.pop()  # Backtrack

            # 2. Choose right parenthesis
            # Right parenthesis count cannot exceed left parenthesis count (i.e. must guarantee validity)
            close_count = i - open_count
            if close_count < open_count:
                path.append(')')
                dfs(i + 1, open_count)
                path.pop()  # Backtrack

        # Start recursion from position 0, initially 0 left parentheses
        dfs(0, 0)
        return ans

javascript

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    const ans = [];
    const path = [];

    function dfs(i, open) {
        if (i == 2 * n) {
            ans.push(path.join(''));
            return;
        }

        if (open < n) {
            path.push('(');
            dfs(i + 1, open + 1);
            path.pop();
        }

        if (i - open < open) {
            path.push(')');
            dfs(i + 1, open);
            path.pop();
        }
    }

    dfs(0, 0);
    return ans;
};

Complexity Analysis

• Time Complexity: O(4^n)
• Space Complexity: O(n * 4^n)

Links

22. Generate Parentheses (English)

22. 括号生成 (Chinese)