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.