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 core idea is to use backtracking. We'll recursively explore all possible placements of opening and closing parentheses, keeping track of the balance using two variables:

1. open: Counts the number of opening parentheses used so far.
2. close: Counts the number of closing parentheses used so far.

At each step, we have three possibilities:

• Add an opening parenthesis ((): If open < n (we haven't used all opening parentheses), we add an opening parenthesis, increment open, and recursively call the function.
• Add a closing parenthesis ()): If close < open (we have more opening parentheses than closing parentheses), we add a closing parenthesis, increment close, and recursively call the function.
• Base Case: If open == n && close == n (we've used all parentheses), we've found a valid combination, so we add it to the result.

Explanation

The backtracking approach systematically explores all valid combinations. The constraints open < n and close < open ensure that we only generate well-formed parentheses. The open < n condition prevents adding more opening parentheses than allowed, while close < open prevents adding a closing parenthesis before its matching opening parenthesis, thus avoiding invalid combinations like )(.

Code

#include <string>
#include <vector>

using namespace std;

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", n, 0, 0);
        return result;
    }

private:
    void backtrack(vector<string>& result, string current, int n, int open, int close) {
        if (open == n && close == n) {
            result.push_back(current);
            return;
        }

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

Complexity

• Time Complexity: O(4ⁿ / n^1.5). This is a Catalan number, representing the number of valid combinations. While the naive approach would explore a much larger space, the constraints prune many invalid paths.
• Space Complexity: O(4ⁿ / n^1.5) in the worst case, due to storing all generated parentheses combinations. The recursion depth is also O(n).