Generate Parentheses medium

Problem Statement

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

For example:

  • generateParenthesis(3) should return ["((()))","(()())","(())()","()(())","()()()"]

Example 1

Input: n = 3

Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2

Input: n = 1

Output: ["()"]

Steps

  1. Backtracking: We'll use backtracking to explore all possible combinations. This involves recursively building strings of parentheses.

  2. Base Case: If the length of the current string is 2n, meaning we've used all n pairs, we add it to the result.

  3. Constraints: We need to ensure we don't create invalid parentheses. Two key constraints are:

    • The number of open parentheses (open) must always be greater than or equal to the number of closed parentheses (close). This prevents scenarios like ) (.
    • The number of open parentheses cannot exceed n.

  4. Recursive Calls: In each recursive step:

    • If open < n, we can add an opening parenthesis (.
    • If close < open, we can add a closing parenthesis ).

  5. Return Value: The function returns an array of strings, each representing a valid combination of parentheses.

Explanation

The backtracking algorithm systematically explores all possible combinations of parentheses. The constraints (open >= close and open <= n) prune the search space by avoiding invalid combinations. Each recursive call either adds an opening or closing parenthesis, depending on whether it's valid to do so. The base case adds the complete combination to the result when all n pairs are used.

Code

function generateParenthesis(n: number): string[] {
    const result: string[] = [];

    function backtrack(s: string, open: number, close: number): void {
        if (s.length === 2 * n) {
            result.push(s);
            return;
        }

        if (open < n) {
            backtrack(s + '(', open + 1, close);
        }
        if (close < open) {
            backtrack(s + ')', open, close + 1);
        }
    }

    backtrack("", 0, 0);
    return result;
}


//Example Usage
console.log(generateParenthesis(3)); // Output: ['((()))', '(()())', '(())()', '()(())', '()()()']
console.log(generateParenthesis(1)); // Output: ['()']

Complexity

  • Time Complexity: O(4n / n1.5). This is a Catalan number, representing the number of valid combinations. While the naive approach explores a larger space, the constraints significantly reduce the actual work.

  • Space Complexity: O(4n / n1.5) in the worst case due to the storage of results, which is again related to the Catalan number. The recursive call stack space also contributes but is proportionally smaller.