DSA - generate-parentheses - C++,Dynamic Programming

Hey, so today we are going to solve Leetcode - Generate Parentheses

Problem Link- https://leetcode.com/problems/generate-parentheses/

Approach - 1: Dynamic Programming

class Solution {
public:

    vector<string> generateParenthesis(int n) {

     vector<vector<string>> dp(n+1, vector<string>());
     dp[0].emplace_back("");

     for(int i =1; i<=n; i++){
      for(int j =0; j<i; j++){
         for(string str1 : dp[j]) {
            for(string str2 : dp[i-j-1]){
              string s = '(' + str1 + ')' + str2;
              dp[i].emplace_back(s);
            }
          }
        }
      }


      return dp[n];
    }
}

Here's how it works:

We define a function generateParenthesis that takes an integer n as input and returns a vector of strings containing all possible valid combinations of parentheses of length 2n.
Inside the function, we create a 2D vector dp of size n+1, where dp[i] represents the set of all possible valid combinations of parentheses of length 2i.
We initialize dp[0] to contain a single empty string "", since an empty string is the only valid combination of parentheses of length 0.
We then use a nested loop to generate all possible valid combinations of parentheses of length 2i. The outer loop iterates over i from 1 to n, and the inner loop iterates over j from 0 to i-1.
Inside the inner loop, we use two nested loops to concatenate all possible valid combinations of parentheses of length j and i-j-1, and store them in dp[i].
Finally, we return dp[n], which contains all possible valid combinations of parentheses of length 2n.

Approach - 2: Recursion

class Solution {
public:
    void solve(string op, int open, int close, vector<string>&ans){
    if(open == 0 && close == 0){
     ans.emplace_back(op);
     return;
     }

    if(open == close){
    string op1 = op;
    op1.emplace_back('(');
    solve(op1, open-1, close, ans);
    }

    else if(open == 0){
    string op1 = op;
    op1.emplace_back(')');
    solve(op1, open, close-1, ans);
     }

    else if(close == 0){
     string op1 = op; 
     op1.emplace_back('(');
     solve(op1, open-1, close, ans);
    }

    else {
    string op1 = op, op2 = op; 
    op1.emplace_back('(');
    op2.emplace_back(')');
    solve(op1, open-1, close, ans);
    solve(op2, open, close-1, ans);
    }
}
    vector<string> generateParenthesis(int n) {
    int open = n, close = n;
    string op ="";
    vector<string> ans; 
    solve(op, open, close, ans);
    return ans;
    }
}

Here's how it works:

We take a count of open and closed parenthesis we have with us. It will be initialised with the value n , we have a helper string op and ans as our result which we will return at the end.
In our helper function named solve() , if we have open and close both being equal to 0, then it means we are no more left with any of those types of parenthesis to work with and will simply add our existing op string to ans and return to the main function.
If we see our open and close to being equal it means we have to use our open bracket as for now we don't have any open brackets. Eg:- for open == close we can have our op string as op = "", "()", "()()", and many more
If we have open == 0 then you have no choice but to use the close bracket and push them in the op string.
If you have close==0 then you have no choice but to use the open bracket and push them in the op string.
For the rest of the cases when open > close you have a string where you can either add more open brackets or add close brackets. So here two options are available and we will utilise both of them and will recurse through them.