Generate Parentheses

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

Approach: Backtracking with Open and Close Counters

Algorithm

1. Only add an opening parenthesis when the count of open parentheses is less than n
2. Only add a closing parenthesis when the count of close parentheses is less than the count of open parentheses (keeps the string well-formed)
3. When the total length reaches 2 * n, a complete combination has been found
4. Backtrack by removing the last character before trying the next choice

Time & Space Complexity

• Time Complexity: O(4^n / sqrt(n)) - the number of valid combinations is the n-th Catalan number
• Space Complexity: O(n) - depth of the recursion tree (the output list is not counted)

Java Implementation

import java.util.ArrayList;
import java.util.List;

public class GenerateParentheses {

    /**
     * Generate all combinations of well-formed parentheses.
     * @param n Number of pairs
     * @return List of valid parentheses strings
     */
    public static List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, new StringBuilder(), 0, 0, n);
        return result;
    }

    private static void backtrack(List<String> result, StringBuilder current,
                                  int open, int close, int n) {
        if (current.length() == 2 * n) {
            result.add(current.toString());
            return;
        }

        if (open < n) {
            current.append('(');
            backtrack(result, current, open + 1, close, n);
            current.deleteCharAt(current.length() - 1);
        }

        if (close < open) {
            current.append(')');
            backtrack(result, current, open, close + 1, n);
            current.deleteCharAt(current.length() - 1);
        }
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 3");
        System.out.println("Output: " + generateParenthesis(3));
        // Expected: ["((()))","(()())","(())()","()(())","()()()"]

        System.out.println("Input: n = 1");
        System.out.println("Output: " + generateParenthesis(1));
        // Expected: ["()"]
    }
}

Example Walkthrough

For n = 3, the recursion explores choices where close < open and open < n:

1. Start with empty string, open=0, close=0
2. Always add ( first: ”(”, open=1
3. Branch into adding more ( or ) as long as the conditions hold
4. Valid full-length strings of 6 characters are recorded

Final output: ["((()))","(()())","(())()","()(())","()()()"].

Key Points

1. Well-formedness: A closing parenthesis is only allowed after an opening one (close < open)
2. Branch Pruning: No invalid prefixes are ever generated, so no explicit validity check is needed
3. Catalan Number: The number of valid strings equals the n-th Catalan number
4. StringBuilder: Appending and deleting the last character makes backtracking efficient
5. Early Termination: The recursion stops when the length reaches 2 * n