22. Generate Parentheses

Got it, Rakesh 🚀 Let’s turn this into a neat blog post. I’ll explain the problem, walk through the approach, give a complexity analysis, and finally embed your visualization iframe.

Here’s a polished draft for your blog:

---

Generate Parentheses — Explained with Backtracking & Visualization

One of the classic problems in coding interviews (especially LeetCode #22) is "Generate Parentheses". It’s a great way to understand backtracking, recursion, and how constraints guide the search space.

---

Problem Statement

Given n pairs of parentheses, generate all possible combinations of well-formed parentheses.

Example:

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

---

Approach

This problem is a textbook case for backtracking.
We want to build strings step by step, only adding characters when they keep the parentheses valid.

Rules for Valid Parentheses:

1. We can add an opening parenthesis "(" as long as we haven’t used up all n.
2. We can add a closing parenthesis ")" only if the number of closing brackets is less than the number of opening ones so far (to avoid invalid strings like ")(").

We use a stack to build the current sequence and a recursive function to explore all possibilities.

---

Code Implementation

/**
 * @param {number} n
 * @return {string[]}
 */
var generateParenthesis = function (n) {
    let stack = [];
    let res = [];

    const backtrack = (openN, closedN) => {
        // Base case: if both counts reach n, we found a valid string
        if (openN === n && closedN === n) {
            res.push(stack.join(""));
            return;
        }

        // Add "(" if we still have openings left
        if (openN < n) {
            stack.push("(");
            backtrack(openN + 1, closedN);
            stack.pop(); // backtrack
        }

        // Add ")" if it's valid
        if (openN > closedN) {
            stack.push(")");
            backtrack(openN, closedN + 1);
            stack.pop(); // backtrack
        }
    };

    backtrack(0, 0);
    return res;
};

---

Complexity Analysis

• Time Complexity: Each valid sequence has length 2n. The number of valid sequences is the nth Catalan number:

$$
C_n = \frac{1}{n+1} \binom{2n}{n}
$$

So, the complexity is O(Cn × n) (since joining each sequence takes O(n) time).

• Space Complexity:

  • The recursion depth is at most 2n.
  • We use a stack of size 2n in the worst case.
  • Result storage takes O(Cn × n).

So overall space complexity is O(Cn × n).

---

Visualization 🎨

Here’s an interactive visualization of the backtracking tree:

---

Final Thoughts

This problem is a perfect introduction to backtracking. It teaches how to explore a search space while pruning invalid paths early. Once you master this, you’ll notice a similar structure in problems like N-Queens, Combinations, and Subsets.

👉 Tip: When stuck in a backtracking problem, always ask:

• “What choices do I have at this step?”
• “What constraints stop me from making a choice?”

---