Generate Parentheses - Mastering Backtracking

Today, we're tackling a classic example of this: "Generate Parentheses" (LeetCode #22).

This problem challenges us to generate all "well-formed" parentheses strings given a number n (representing n pairs of parentheses). This is a perfect scenario for applying the powerful backtracking algorithm.

---

Understanding the Problem:

You are given an integer n. Your task is to return a list of all possible strings that represent "well-formed" parentheses using exactly n pairs of parentheses.

What does "well-formed" mean?

• Every opening parenthesis ( must have a corresponding closing parenthesis ).

• A closing parenthesis ) cannot appear before its corresponding opening parenthesis.

• The total number of ( must equal the total number of ).

Examples:

• Input: n = 1

  • Output: ["()"] (1 open, 1 close)

• Input: n = 3

  • Output: ["((()))", "(()())", "(())()", "()(())", "()()()"] (3 open, 3 close for each)

---

My Thought Process & Approach (Backtracking / Recursive Exploration):

This problem is a classic "generate all combinations" type, which immediately points towards a backtracking (recursive) solution. At any point while building a parenthesis string, we have a choice: either add an opening parenthesis ( or a closing parenthesis ). We explore these choices, and if a path becomes invalid or reaches a base case, we "backtrack" to try another path.

The Decision Tree and Pruning Rules:

The key to efficient backtracking is to prune (stop exploring) paths that are guaranteed not to lead to a valid solution. We can define our recursive function (helper in the code) with parameters that track the current state:

• str: The list to collect all valid generated strings.

• sb: The StringBuilder representing the current parenthesis string being built.

• A (or n): The target number of parenthesis pairs.

• open: The count of opening parentheses already added to sb.

• close: The count of closing parentheses already added to sb.

Base Case (When to stop and add to result):

• When the total number of parentheses (open + close) equals 2 * A (meaning we've used all n open and n close parentheses), we have a complete string. If it's valid by our rules (which our pruning ensures), we add sb.toString() to our str list and return.

Recursive Steps (When to make choices and prune invalid paths):

1. Rule for Adding (:

   • We can add an opening parenthesis ( ONLY IF the number of open parentheses we've placed so far (open) is less than the total allowed n (A).

   • If open < A:

     • Append ( to sb.

     • Recursively call helper with open + 1.

     • Backtrack: Remove the ( from sb to explore other possibilities.

2. Rule for Adding ):

   • We can add a closing parenthesis ) ONLY IF the number of closing parentheses we've placed so far (close) is strictly less than the number of opening parentheses we've already placed (open). This is crucial to ensure well-formedness (we never close a bracket before opening one).

   • If close < open:

     • Append ) to sb.

     • Recursively call helper with close + 1.

     • Backtrack: Remove the ) from sb to explore other possibilities.

By following these rules, our recursion systematically builds all possible well-formed parenthesis strings, discarding invalid paths early.

---

Java Code Implementation:

class Solution {
    public List<String> generateParenthesis(int n) {
        int open =0;
        int close =0;
        ArrayList<String> str = new ArrayList<String>();
        StringBuilder sb = new StringBuilder();
        helper(str, sb, n,open,close);
        return str;
    }
    public void helper(ArrayList<String> str, StringBuilder sb, int A, int open, int close){
        if(open + close == 2*A){
            str.add(sb.toString());
            return;
        }
        if(open<A){
            sb.append('(');
            helper(str,sb,A,open+1,close);
            sb.deleteCharAt(sb.length() - 1);
        }
        if(close<open){ sb.append(')');
            helper(str,sb,A,open,close+1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

---

Time and Space Complexity Analysis:

• Time Complexity: < O(2^N)

  • When thinking about recursive problems with choices, it's common to initially consider a branching factor that leads to complexities like O(2^N) or O(4^N) (since the string length is 2N).

  • However, in our backtracking solution for "Generate Parentheses," we use strict pruning rules (open < n and close < open). These rules are incredibly effective at cutting down the search space. We don't explore invalid paths (like adding a ) before an ( or using too many of either type).

  • Because of this aggressive pruning, the actual number of states our algorithm explores is significantly less than a full 2^(2N) or 4^N search tree. While it's still exponential, it's bounded by a tighter factor, making it < O(2^N).

• Space Complexity: O(N)

  • For recursive algorithms, when we talk about space complexity, we're primarily referring to the auxiliary space used by the algorithm during its execution.

  • In this solution, the main auxiliary space consumer is the recursion call stack. The maximum depth of our helper function calls will be 2*n (when a complete parenthesis string of length 2*n is being built).