22. Generate Parentheses

📝 Problem Details

• Title: 22. Generate Parentheses
• Link: https://leetcode.com/problems/generate-parentheses/
• Difficulty: Medium
• Tags/Categories: Stack Dynamic-Programming Backtracking Strings
• Neetcode Reference: Video Link

---

🔍 Problem Understanding

What are considered “well-formed” parentheses?

• has an opening an closing bracket in an appropriate order

We are given a value n, of which we need to generate all possible combinations of well formed parentheses

---

🎯 Key Insights

- this is a permutation / combinatorics question 
- was initially unsure how a stack could be used to solve this problem
- instead of an explicit stack datastructure, we can employ the call stack through recursion to do are computation of permutations 
- this is a "backtracking" / dynamic programming question 

---

🔑 Approach

1. recursive backtracking
	- use recursion to explore all possible combinations of parentheses
	- maintain a count of open and close parentheses used so far
	- only add an opening parenthesis "(" if open < n
	- only add a closing parenthesis ")" if close < open, ensuring a valid order of parentheses

2. base case
	- if the counts of both open and close parentheses reach n, the current combination is valid and added to the result

3. optimization 
	- the call stack acts as an implicit "stack" to handle backtracking, avoiding the need for an explicit stack data structure

---

⌛ Complexity Analysis

Time Complexity: O(4^n  / sqrt(n))
	- this comes from the catalan number formula that determines the count of valid combinations 
	- verifying each combination takes O(n) time which adds to the total complexity

Space Complexity: O(2n)
	- the recursive call stack
	- the depth of the tree is proportional to the total parentheses used 

---

💻 Implementation of Solution

class Solution {
private:
    void generate(int n, int open, int close, string str, vector<string>& result) {
        if(open == n && close == n) {
            result.push_back(str);
            return;
        }
        if(open < n) {
            generate(n, open + 1, close, str + "(", result);
        }
        if(open > close) {
            generate(n, open, close + 1, str + ")", result);
        }
    }
 
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        generate(n, 0, 0, "", result);
        return result;    
    }
};