Generate Parentheses medium

Problem Statement

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

Steps

The problem can be solved using backtracking. We maintain a string to represent the current parentheses combination being built and track the number of open and closed parentheses.

1. Base Case: If the number of open parentheses equals n and the number of closed parentheses also equals n, we've formed a valid combination. Add it to the result list and backtrack.

2. Recursive Step:

   • If the number of open parentheses is less than n, we can add an opening parenthesis (. Recursively call the function with an incremented open parenthesis count.
   • If the number of closed parentheses is less than the number of open parentheses, we can add a closing parenthesis ). Recursively call the function with an incremented closed parenthesis count.

3. Backtracking: After each recursive call, remove the last added parenthesis from the current string to explore other possibilities.

Explanation

The backtracking approach systematically explores all possible combinations of parentheses. By keeping track of open and closed parentheses, we ensure that we only generate well-formed combinations (where the number of closed parentheses never exceeds the number of open parentheses at any point). The base case ensures that we stop when we've created a complete, valid combination.

Code

using System;
using System.Collections.Generic;

public class Solution {
    public IList<string> GenerateParenthesis(int n) {
        IList<string> result = new List<string>();
        Backtrack(result, "", 0, 0, n);
        return result;
    }

    private void Backtrack(IList<string> result, string current, int open, int close, int n) {
        if (open == n && close == n) {
            result.Add(current);
            return;
        }

        if (open < n) {
            Backtrack(result, current + "(", open + 1, close, n);
        }

        if (close < open) {
            Backtrack(result, current + ")", open, close + 1, n);
        }
    }
}

Complexity

• Time Complexity: O(4^n / n^(3/2)), which is the nth Catalan number. This is because the number of valid combinations grows exponentially with n.
• Space Complexity: O(4^n / n^(3/2)) in the worst case, due to the recursive call stack and the storage of the result list. The space used by the recursive stack can also be considered O(n) in the average case because the depth of the recursion is at most 2n.