https://mycode.prepbytes.com/problems/recursion/PRAGYAGOMED

Please try to solve this question using recursion and memorization don’t use Tabulation Method of DP because I have not studied it Yet .

Please Help !

https://mycode.prepbytes.com/problems/recursion/PRAGYAGOMED

Please try to solve this question using recursion and memorization don’t use Tabulation Method of DP because I have not studied it Yet .

Please Help !

2 Likes

Hey k_purushottam

I have solved this problem using Recursion and it got AC without memoization.Just think in a way that you have 2 choices every time either you pick character from 1st string or 2nd string and pass that to recursion and backtrack so that you can skip it for further strings and by running the code I founded that it finds the exacts string (not the duplicates as every time we either pick that char or skip that) (try pen and paper and you’ll see strings are always distinct).

#include

#include<bits/stdc++.h>

#include

#include

#include<math.h>

#include

#include<stdio.h>

#include

#include

#include

#include<unordered_map>

#include

#include

#include

#include

#define int long long int

#define ld long double

#define pi 3.1415926535897932384626433832795028841971

#define MOD 1000000007

#define MOD1 998244353

#define print(vec) for (int i = 0; i < vec.size(); i++) cout << vec[i] << " "; cout << “\n”;

using namespace std;

int ans = 0;

string s, t;

int n, m;

void solve(int i, int j, int sizeofstring)

{

if (i >= n)

{

while (j < m)

{

sizeofstring++;

j++;

}

}

if (j >= m)

{

while (i < n)

{

sizeofstring++;

i++;

}

}

if (sizeofstring == n + m)

{

ans++;

return;

}

sizeofstring++;

solve(i + 1, j, sizeofstring);

sizeofstring–;

```
sizeofstring++;
solve(i, j + 1, sizeofstring);
sizeofstring--;
```

}

int32_t main() {

#ifndef ONLINE_JUDGE

freopen(“input.txt”, “r”, stdin);

freopen(“output.txt”, “w”, stdout);

#endif

ios_base::sync_with_stdio(false);

cin.tie(NULL);

int tt;

cin >> tt;

while (tt–)

{

ans = 0;

cin >> s >> t;

n = s.size();

m = t.size();

solve(0, 0, 0);

cout << ans << “\n”;

}

return 0;

}

If you have any doubts feel free to ask

1 Like

Thanks for the help

This solution can have some repeated output strings such as for an input

strings “ab” and “daa”

each string accourding to this rule can be : -

Input :-

ab daa

Output :-

abdaa

adbaa

adaba

adaab

dabaa

daaba

daaab

daaba

daaab

daaab

10

But if you just consider all unique than answer will be 7

Thanks for the help again . My physical and Mental heath was not good so it took me a lot of time to reply sorry for that .

Your solution is correct as it is also accepting duplicate values.