Printing all the ways to transform S to T.

Recently in an Interview,I was asked this question.. Given a String S and another string T,You have to change S to T using following steps only - You can push a character from S to the stack and pop an element from the stack...

Now if a push operation is denoted by 0 and pop is denoted by 1, generate all possible valid strings that can transform S to T.

Given that transformation will always be possible and |S| = |T| <= 15.

For Ex - S = "MADAM" T = "ADAMM" The steps to convert will be - push M (0) push A (0) pop A (1) push D (0) pop D (1) push A (0) pop A (1) push M (0) pop M (1) pop M (1)

So "0010101011" is a valid string,I need to generate all the valid strings.. All i can come up with was this code,which was able to generate a single valid string..Can anyone help me out in how to generate each valid string. (Note: Bitmasking approach is not allowed)

include<bits/stdc++.h>

using namespace std; // i -> upto what position in S we are done // j -> upto what position in T we have completed // o for push //1 for pop bool temp[32] = {0}; stack st; int l = 0,k = 0;

void solve(string& S,string& T,int i,int j) { if(k == 2*l — 1) { for(int i = 0;i <= k;i++) cout << temp[i] << " "; cout << endl; return ; }

if(i < 0    || j < 0   ||    i > l ||   j > l)
    return;
if(st.size())
if(T[j] == st.top())
{
    st.pop();
    temp[k++] = 1;
    solve(S,T,i,j + 1);
    k -= 1;
}

if(T[j] == S[i])         // Both current charcters matches each other
{
    st.push(S[i]);
    temp[k++] = 0;
    st.pop();
    temp[k++] = 1;
    solve(S,T,i+1,j+1);
    k -= 2;
}

if(T[j] != S[i])
{
       // Keep pushing characters from S,and increase i until they do not matches
       st.push(S[i]);
       temp[k++] = 0;
       solve(S,T,i+1,j);
       k -= 1;

}

}

int main() { ios_base::sync_with_stdio(0); string S,T; cin >> S; cin >> T; // cout << st.top(); l = S.length(); solve(S,T,0,0); return 0; }