CODEWITHSUNDEEP
c++algorithmrecursiondynamic-programming
user126746
user126746

Reputation: 21

Balance ordering parenthesis via Dynamic programing

Hi from the very famous book Code to Crack i come across a question :

Implement an algorithm to print all valid (e.g., properly opened and closed) combinations of n-pairs of parentheses.

Example:

input: 3 (e.g., 3 pairs of parentheses)
output: ()()(), ()(()), (())(), ((()))

#include <iostream>
#include <string>

using namespace std;

void _paren(int l,int r,string s,int count);
void paren(int n)
{
    string s="";
    _paren(n,n,s,n);
}

void _paren(int l,int r,string s,int count){

    if(l<0 || r<0)
        return;
    if(l==0 && r==0)
        cout<<s<<endl;
    else{
        if(l>0)
        {
            _paren(l-1,r,s+"(",count+1);
        }
        if(r>l)
            _paren(l,r-1,s+")",count+1);                    
    }
}
int main(){
    int n;
    cin>>n;
    paren(n);
    return 0;
}

This is a recursive approach I tried for it . I am pretty sure that we can solve this through dynamic programming as well , as we are already using a lot of value again and again , but I have no idea how to implement this through Dynamic programming I tried tabular bottom up approach but couldnt work out. Please help me out just the basic idea on how to work with this

Upvotes: 2

Views: 1201

Answers (3)

cuv
cuv

Reputation: 1229

I'm very late to the party, but I stumbled across this problem just now and I was asking myself the same question regarding the dynamic programming approach. Maybe this will help somebody in the future.

I managed to find this solution (not mine) on leetcode:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

// memoization (dynamic programming)
// store solutions for n = 0, 1, 2, etc..
vector<vector<string>> dp = {{""}, {"()"}};

vector<string> generateParenthesis(int n) {
    if (dp.size() == 2 && n > 1) dp.resize(n + 1);
    if (dp[n].size()) return dp[n];
    vector<string> ans;
    for(int i = 0; i < n; ++i) {
        vector<string> a, b;
        a = generateParenthesis(i), 
        b = generateParenthesis(n - i - 1);
        for(string &el1 : a)
            for(string &el2 : b) 
                ans.push_back("(" + el1 + ")" + el2);
    }
    dp[n].swap(ans);
    return dp[n];
}


int main() {
    int n = 4;
    vector<string>solution = generateParenthesis(n);
    for (string& s: solution) {
        cout << s << endl;
    }
    return 0;
}

As others mentioned, this seems like a bad idea to implement due to memory constraints.

Again, this solution does not belong to me. I cannot give credit because the author is unknown.

Upvotes: 0

Ralor
Ralor

Reputation: 369

DP can reduce count of traversed states by choosing the optimal solution every call. It also help you to reuse calculated values. There is no calculations, every valid state must be visited, and non-valid states can be avoided by if( ).

I suggest you to implement some another recursion (at least without copying new string object after call, just declare global char array and send it to output when you need).

My idea of recursion is

char arr[maxN]; int n; // n is string length, must be even though
void func(int pos, int count) { // position in string, count of opened '('
   if( pos == n ) {
      for(int i = 0; i < n; i++)
         cout << char(arr[i]);
      cout << "\n";
      return;
   }
   if( n-pos-1 > count ) {
      arr[pos] = '('; func(pos+1,count+1);
   }
   if( count > 0 ) {
      arr[pos] = ')'; func(pos+1,count-1);
   }
}

I didn't checked it, but the idea is clear I think.

Upvotes: 1

Ukkonen
Ukkonen

Reputation: 21

DP does not really help you. The recursive algorithm is time and space optimal!

In fact, there is a reason not to use DP: the memory requirements! This will be huge.

A better algorithm is to have one character array that you pass in, have the recursive method modify parts of it and print that when needed. I believe that solution is given in the book you mention.

Upvotes: 2

Related Questions