Generate Parentheses – LeetCode Solution (C++)

Generating valid parentheses combinations is a fundamental backtracking problem that is frequently asked in coding interviews. In this article, we will cover the optimal approach, step-by-step explanations, dry runs, alternative methods, and complexity analysis.

Problem Statement

LeetCode 22: Generate Parentheses

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:

["()"]

Optimal Approach – Backtracking (DFS)

Since we need all valid combinations, a brute-force approach would be inefficient.
Instead, we use backtracking to explore all possible sequences while maintaining a valid parenthesis structure.

Key Idea

A valid sequence must contain n open (() and n close ()) brackets.
At any point:
- We can add an open bracket (() if the count of ( is less than n.
- We can add a close bracket ()) if the count of ) is less than the count of (.
Once both ( and ) reach n, a valid sequence is formed.

Time Complexity

O(4^n / sqrt(n)) → Number of valid sequences follows the Catalan number series.
Exponential growth, but optimal for this problem.

Space Complexity

O(N) → Recursion depth reaches 2N in worst case.

C++ Solution (LeetCode Compatible)

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

private:
    void backtrack(vector<string>& result, string current, int open, int close, int n) {
        if (current.size() == 2 * n) { // Base case: valid combination
            result.push_back(current);
            return;
        }
        if (open < n) backtrack(result, current + "(", open + 1, close, n); // Add '(' if possible
        if (close < open) backtrack(result, current + ")", open, close + 1, n); // Add ')' if valid
    }
};

Step-by-Step Code Explanation

Initialize the Result List
- vector<string> result; stores valid combinations.
Recursive Backtracking Function
- backtrack(result, "", 0, 0, n); starts with an empty string and 0 open/close counts.
Base Case – Stop Recursion
- If current.size() == 2 * n, store the valid combination.
Recursive Case – Add Parentheses
- Add ( if open < n.
- Add ) if close < open.

Dry Run (Step-by-Step Execution)

Example Input

n = 3

Recursive Calls

Step	Open Count	Close Count	Current String	Action
1	1	0	`(`	Add `(`
2	2	0	`( (`	Add `(`
3	3	0	`(((`	Add `(`
4	3	1	`((())`	Add `)`
5	3	2	`((()))`	Add `)`
6	3	3	`((()))`	Valid combination ✅
7	Backtrack	2	`(()`	Add `)`
8	3	2	`(()())`	Add `)`
9	3	3	`(()())`	Valid combination ✅

Final Output

["((()))","(()())","(())()","()(())","()()()"]

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Notes
Brute Force (Generate All Strings & Filter)	O(2^(2N))	O(2N)	❌ Generates invalid sequences, high overhead
Backtracking (Optimal Approach) ✅	O(4^N / sqrt(N))	O(N)	✅ Efficient, avoids invalid cases
Dynamic Programming (DP Approach)	O(2^N)	O(N^2)	❌ Slower than backtracking
Stack-based Validation	O(N log N)	O(N)	❌ Adds extra memory for stack operations

Why Backtracking is the Best?

✔ Avoids unnecessary sequences.
✔ Only explores valid solutions.
✔ Minimal extra space.

Conclusion

Best approach: Backtracking (DFS)
Why? Efficiently explores only valid sequences.
Alternative: DP approach (suboptimal due to extra space).
Practice More:

Would you like more detailed tutorials like this? Let me know! 🚀

LeetCode 22: Generate Parentheses