That seems like an very complex way to frame the problem.
Given the two arrays of length n and m, each of the result arrays in your answer are going to be length n+m. Think of each element in those arrays as a binary decision between choosing the next element of each array - there will be C(n+m,n) possible outcomes - and this is just a bit string where a 0 means take the next element from the first array and a 1 from the second array. Once you see this, it is just a matter of generating all length n+m bit strings with exactly n 0-bits.
Great point that since relative order is fixed, it's just a binary decision.
A similar problem (with the same solution described) is "balls and bins" [1]: you have k identical balls and n bins - how many ways are there to place the balls in the bins? It blew my mind in intro to discrete math when we reconsidered the problem with instead of n bins, (n-1) bin dividers. Then simply choose where to place the (n-1) dividers out of (k+n-1) places for all of your objects, and you're done!
Given the two arrays of length n and m, each of the result arrays in your answer are going to be length n+m. Think of each element in those arrays as a binary decision between choosing the next element of each array - there will be C(n+m,n) possible outcomes - and this is just a bit string where a 0 means take the next element from the first array and a 1 from the second array. Once you see this, it is just a matter of generating all length n+m bit strings with exactly n 0-bits.
This is the next permutation problem which can be done in constant space and linear time and very efficiently too. C++ even has an STL function for it: http://www.cplusplus.com/reference/algorithm/next_permutatio...
Your starting array is '0011' in his example, then keep generating the next permutation in a loop until exhausted so '0101', '0110', etc...
edit: here's a cute bit hack for it too: https://graphics.stanford.edu/~seander/bithacks.html#NextBit...