algoadvance

Leetcode 22. Generate Parentheses

Problem Statement

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

Clarifying Questions

  1. Input Constraints:
    • What is the range of n?
      • Typically n can range from 1 to 8 or 10 for competitive programming problems due to the exponential growth in the number of combinations.
  2. Output Requirements:
    • Should the output be a list of strings where each string represents a valid combination of parentheses?

Strategy

To solve this problem, a common approach is to use backtracking. The idea is to build the parentheses string step by step and ensure that at every step the string being built is a valid prefix of some valid well-formed parentheses combination.

  1. Recursive Function Definition:
    • Define a recursive function that takes the current state of the string, number of open brackets, and number of close brackets.
    • Base Case: When the current length of the string is equal to 2 * n, add the string to the result list.
    • For every recursive call, you can:
      • Add an open parenthesis if it’s allowed (i.e., the number of open parentheses used so far is less than n).
      • Add a close parenthesis if it’s allowed (i.e., the number of close parentheses used so far is less than the number of open parentheses used).

Code

#include <vector>
#include <string>
#include <iostream>

using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        generateParenthesisRecursive(result, "", 0, 0, n);
        return result;
    }
    
private:
    void generateParenthesisRecursive(vector<string>& result, string current, int open, int close, int n) {
        if(current.size() == n * 2) {
            result.push_back(current);
            return;
        }
        
        // Try adding an open parenthesis if we can
        if(open < n) {
            generateParenthesisRecursive(result, current + "(", open + 1, close, n);
        }
        
        // Try adding a close parenthesis if we can
        if(close < open) {
            generateParenthesisRecursive(result, current + ")", open, close + 1, n);
        }
    }
};

// Example usage:
int main() {
    Solution solution;
    int n = 3;
    vector<string> result = solution.generateParenthesis(n);
    for(const string& combination : result) {
        cout << combination << endl;
    }
    return 0;
}

Time Complexity

The time complexity of this approach is O(4^n / sqrt(n)). This is derived from the fact that the number of valid permutations of n pairs of parentheses is the Catalan number, which is C(n) = (1 / (n + 1)) * (2n choose n).

Thus, the number of function calls grows exponentially with n, explaining the exponential nature of 4^n. The division by sqrt(n) comes from the combinatorial reduction factor related to Catalan numbers.

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