algoadvance

Leetcode 22. Generate Parentheses

Problem Statement

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

Example:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Clarifying Questions

1. Q: Is there a maximum value for n? A: No explicit maximum value is given, but typical constraints are 0 <= n <= 8 due to exponential growth of combinations.

2. Q: Should the output list be in any specific order? A: No, any order of well-formed parentheses is acceptable.

Strategy

1. Backtracking Approach:
   • Use a recursive function to build the string of parentheses.
   • Keep track of the number of open and close parentheses used.
   • Ensure the number of open parentheses never exceeds n.
   • Ensure the number of close parentheses never exceeds the number of open parentheses in the partially built string.
   • Append the string to the result list when both open and close counts reach n.

The backtracking approach ensures that all valid combinations are explored and invalid combinations are pruned early in the recursive calls.

Code

Here is the Java implementation of the above strategy:

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

public class GenerateParentheses {

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

    private void backtrack(List<String> 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);
        }
    }
    
    public static void main(String[] args) {
        GenerateParentheses gp = new GenerateParentheses();
        System.out.println(gp.generateParenthesis(3));
    }
}

Time Complexity

The time and space complexity for generating all combinations of well-formed parentheses can be analyzed as follows:

• Time Complexity: O(4^n / sqrt(n))
  • This stems from the fact that the number of valid parentheses combinations is the n-th Catalan number, which is approximately C_n ~ 4^n / (n^(3/2) * sqrt(pi)). For simplicity, the time complexity can be loosely expressed as O(4^n / sqrt(n)).
• Space Complexity: O(n)
  • The depth of the recursion tree is 2n (since we are making two recursive calls and building the string), thus the space used by call stack can go up to O(n).

The above implementation ensures the efficient generation of all valid combinations by pruning invalid sequences early through the use of backtracking.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?