Find all combinations of interleaving two strings. Where am I making mistake?

Question

So have two strings. We need to find all the combinations interleaving the strings, i.e all combination where the order of the position of the characters in both strings are maintained.

For e.g "ab", "cd" should return "abcd" "acbd" "acdb", "cdab", "cabd" and so on

Here's how I think of approaching.

With each iteration, we can take the first character of either first string or second string and add that to the result.

so something like this:

function interleaving(str1, str2, index, res=""){
  interleaving(str1, str2, index+1, res+str1[0])
  interleaving(str1, str2, index+1, res+str2[0])
}

now the base condition is when either of the string gets reduced to empty "" in which case we can simply add the remaining characters of second string. This is where probably I'm going wrong and need help.

So I tried this way:

if(str1.length === i){
  res = res + str2;
}

if(str2.length === i){
  res = res + str1;
}

So tried this way but obviously making mistake somewhere in my approach. Appreciate any help to know where that is.

var res =[];
function interleaving(str1, str2, i=0, newStr=""){
if(str1.length === i){
    newStr = newStr+ str2;
  res.push(newStr);
  return;
}

if(str2.length === i){
    newStr = newStr + str1;
  res.push(newStr);
  return;
}


    interleaving(str1, str2, i+1, newStr+str1[i])
    interleaving(str1, str2, i+1, newStr+str2[i])


}

interleaving("ab", "cd");
console.log(res)

Answer 1

Make distinct indices for both strings and call recursion only for valid branches:

var res =[];
function interleaving(str1, str2, i1=0, i2=0, newStr=""){
  if(str1.length === i1 && str2.length === i2){
    res.push(newStr);
    return;
  }

  if(str1.length > i1)
      interleaving(str1, str2, i1+1, i2, newStr+str1[i1])
  if(str2.length > i2)
       interleaving(str1, str2, i1, i2+1, newStr+str2[i2])
}

interleaving("ab", "cd");
console.log(res)