Printing all the ways to transform S to T.

Recently in a Technical 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)

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<char> 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;
}

I am new to codeforces,sorry if i have done some terrible formatting :|