Generate Parentheses

Problem Statement

Given an integer n, generate all valid combinations of n pairs of parentheses. A combination is valid if every opening parenthesis '(' has a matching closing parenthesis ')', and the sequence is well-formed (no closing before opening). This medium-level problem uses recursion and backtracking to build balanced strings—think of it as crafting perfectly nested expressions!

Example

Input: n = 3

Output: ["((()))", "(()())", "(())()", "()(())", "()()()"] (all 5 valid ways for 3 pairs)

Input: n = 1

Output: ["()"] (only one way for 1 pair)

Code

public class Solution {
    public List generateParenthesis(int n) {
        List result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }
    
    private void backtrack(List result, String current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current);
            return;
        }
        if (open < max) {
            backtrack(result, current + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(result, current + ")", open, close + 1, max);
        }
    }
}
            

def generate_parenthesis(n):
    def backtrack(current, open_count, close_count):
        if len(current) == n * 2:
            result.append(current)
            return
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
    
    result = []
    backtrack("", 0, 0)
    return result

# Example usage
print(generate_parenthesis(3))  # ["((()))", "(()())", "(())()", "()(())", "()()()"]
print(generate_parenthesis(1))  # ["()"]
            

function generateParenthesis(n) {
    function backtrack(current, open, close) {
        if (current.length === n * 2) {
            result.push(current);
            return;
        }
        if (open < n) {
            backtrack(current + "(", open + 1, close);
        }
        if (close < open) {
            backtrack(current + ")", open, close + 1);
        }
    }
    
    let result = [];
    backtrack("", 0, 0);
    return result;
}

// Example usage
console.log(generateParenthesis(3)); // ["((()))", "(()())", "(())()", "()(())", "()()()"]
console.log(generateParenthesis(1)); // ["()"]
            

Explanation

• Base Case: When string length equals 2n (n pairs), add it to the result.
• Choices: Add an opening '(' if fewer than n are used, or a closing ')' if fewer than open.
• Backtracking: Build the string incrementally, exploring all valid paths.
• Flow Example (n=2): "" → "(" → "((" → "(()" → "(())"; backtrack to "()" → "()(" → "()()".
• Validity: Ensures well-formedness by only closing when there’s an unmatched opening.

Note