Generate Parentheses in C++ (Time Complexity: O(4^n / sqrt(n)))

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

A parentheses string is well-formed if and only if:

It is the empty string, or
It can be written as AB (A concatenated with B), where A and B are well-formed, or
It can be written as (A), where A is well-formed.

Example 1:

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

Example 2:

Input: n = 1
Output: ["()"]

Note: 1 <= n <= 8

Understanding the Problem

The core challenge of this problem is to generate all possible combinations of well-formed parentheses given n pairs. This problem is significant in various applications such as validating expressions in compilers, parsing algorithms, and more. A common pitfall is to generate invalid combinations that do not respect the well-formed rule.

Approach

To solve this problem, we can use a backtracking approach. The idea is to build the string step by step, ensuring at each step that the string remains valid. We can start with an empty string and add either an opening or closing parenthesis, ensuring that the number of closing parentheses never exceeds the number of opening ones.

Naive Solution

A naive solution would be to generate all possible strings of length 2n and then filter out the valid ones. However, this approach is not optimal as it generates many invalid strings, leading to unnecessary computations.

Optimized Solution

The optimized solution uses backtracking to generate only valid strings. This approach is more efficient as it prunes invalid paths early in the recursion.

Algorithm

Here is a step-by-step breakdown of the backtracking algorithm:

Start with an empty string and two counters: open and close, both initialized to 0.
At each step, add an opening parenthesis if the number of opening parentheses is less than n.
Add a closing parenthesis if the number of closing parentheses is less than the number of opening parentheses.
Continue this process until the length of the string is 2n.
When the length of the string is 2n, add it to the result list.

Code Implementation


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

using namespace std;

// Helper function for backtracking
void backtrack(vector<string>& result, string current, int open, int close, int max) {
    // If the current string is of the maximum length, add it to the result
    if (current.length() == max * 2) {
        result.push_back(current);
        return;
    }

    // Add an opening parenthesis if we can
    if (open < max) {
        backtrack(result, current + "(", open + 1, close, max);
    }

    // Add a closing parenthesis if we can
    if (close < open) {
        backtrack(result, current + ")", open, close + 1, max);
    }
}

// Main function to generate parentheses
vector<string> generateParenthesis(int n) {
    vector<string> result;
    backtrack(result, "", 0, 0, n);
    return result;
}

// Driver code
int main() {
    int n = 3;
    vector<string> result = generateParenthesis(n);

    for (const string& s : result) {
        cout << s << endl;
    }

    return 0;
}

Complexity Analysis

The time complexity of the backtracking solution is O(4^n / sqrt(n)), which is derived from the Catalan number. The space complexity is O(n) due to the recursion stack.

Edge Cases

Some potential edge cases include:

n = 0: The output should be an empty list.
n = 1: The output should be ["()"].

These edge cases are handled naturally by the backtracking algorithm.

Testing

To test the solution comprehensively, consider the following test cases:

Simple cases like n = 1 and n = 2.
Edge cases like n = 0.
Larger values of n to ensure performance, such as n = 8.

Thinking and Problem-Solving Tips

When approaching such problems, it is essential to:

Understand the problem constraints and requirements thoroughly.
Think about the base cases and how to build the solution incrementally.
Use backtracking to explore all possible solutions while pruning invalid paths early.

Conclusion

Generating well-formed parentheses is a classic problem that helps in understanding backtracking and recursion. By practicing such problems, one can improve their problem-solving skills and gain a deeper understanding of algorithmic techniques.

Additional Resources

For further reading and practice, consider the following resources: