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

1. A valid sequence must contain n open (() and n close ()) brackets.
2. 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 (.
3. 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

1. Initialize the Result List

   • vector<string> result; stores valid combinations.

2. Recursive Backtracking Function

   • backtrack(result, "", 0, 0, n); starts with an empty string and 0 open/close counts.

3. Base Case – Stop Recursion

   • If current.size() == 2 * n, store the valid combination.

4. Recursive Case – Add Parentheses

   • Add ( if open < n.
   • Add ) if close < open.

Dry Run (Step-by-Step Execution)

Example Input

n = 3

Recursive Calls

Final Output

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

Alternative Approaches & Why Not?

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:
  • Valid Parentheses
  • Longest Valid Parentheses
  • Remove Invalid Parentheses

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

Sandip Mhaske

Senior Engineer • Author of 675 guides • Follow for System Design & .NET deep-dives

About