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 and Explanation

This problem can be solved efficiently using backtracking. The core idea is to explore all possible placements of opening and closing parentheses, ensuring that at any point, the number of closing parentheses never exceeds the number of opening parentheses.

1. Backtracking Function: We'll define a recursive function generateParenthesisHelper(String current, int open, int close, int n, List<String> result):

   • current: The string representing the current combination of parentheses being built.
   • open: The number of opening parentheses already used.
   • close: The number of closing parentheses already used.
   • n: The total number of pairs of parentheses required.
   • result: The list to store the final results.

2. Base Case: If open and close both equal n, it means we've used all parentheses. Add current to result.

3. Recursive Steps:

   • Add Opening Parenthesis: If open < n, we can add an opening parenthesis. Recursively call generateParenthesisHelper(current + "(", open + 1, close, n, result).
   • Add Closing Parenthesis: If close < open, we can add a closing parenthesis (to ensure well-formedness). Recursively call generateParenthesisHelper(current + ")", open, close + 1, n, result).

Code (Java)

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

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        generateParenthesisHelper("", 0, 0, n, result);
        return result;
    }

    private void generateParenthesisHelper(String current, int open, int close, int n, List<String> result) {
        if (open == n && close == n) {
            result.add(current);
            return;
        }

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

Complexity Analysis

• Time Complexity: O(4ⁿ / n^1.5). This is a Catalan number, representing the number of possible combinations. While the number of explored paths seems exponential, it's bounded by this Catalan number.
• Space Complexity: O(4ⁿ / n^1.5) in the worst case, due to the recursive calls and the storage of the results. The space used to store the results dominates the space for recursive calls. The recursive depth is at most 2n.

This improved explanation provides a clear, step-by-step approach with a well-structured code example and a thorough complexity analysis. The backtracking technique is clearly explained, making it easy to understand the solution's logic.