Given two strings str1 and str2, write a function that prints all  interleavings of the given two strings. You may assume that all  characters in both strings are differentExample:Input: str1 = AB,  str2 = CDOutput:    ABCD    ACBD    ACDB    CABD    CADB    CDABInput: str1 = AB,  str2 = COutput:    ABC    ACB    CABThe idea comes from Ray Toal:The base case is when one of the two strings are empty:interleave(s1, ) = {s1}interleave(, s2) = {s2}Notice the order of the arguments doesn't really matter, becauseinterleave(ab, 12) = {ab12, a1b2, 1ab2, a12b, 1a2b, 12ab} = interleave(12, ab)So since the order doesn't matter we'll look at recursing on the length of the first string.Okay so let's see how one case leads to the next. I'll just use a  concrete example, and you can generalize this to real code.interleave(, abc) = {abc} interleave(1, abc) = {1abc,a1bc, ab1c, abc1} interleave(12, abc) = {12abc, 1a2bc,1ab2c, 1abc2, a12bc, a1b2c, a1bc2, ab12c, ab1c2 abc12}So everytime we added a character to the first string, we formed the  new result set by adding the new character to all possible positions  in the old result set. Let's look at exactly how we formed the third  result above from the second. How did each element in the second  result turn into elements in the third result when we added the 2?1abc => 12abc, 1a2bc, 1ab2c, 1abc2 a1bc => a12bc,a1b2c, a1bc2 ab1c => ab12c, ab1c2 abc1 => abc2Now look at things this way:1abc => {1 w | w = interleave(2, abc)} a1bc => {a1 w | w =interleave(2, bc)} ab1c => {ab1 w | w = interleave(2, c)}abc1 => {abc1 w | w = interleave(2, )}The following is my code building on top of the above idea.  Can anyone help me verify it? void interleaving(const string& s2, string result, int start, int depth){    if(depth == s2.size())        cout << result << endl;    else    {        for(int i = start; i <= result.size(); ++i)        {            result.insert(i, 1, s2[depth]);            interleaving(s2, result, i+1, depth+1);            result.erase(i, 1);        }    }}int main(){    string s1();    string s2(12);    string result(s1);   interleaving(s2, result, 0, 0);        system(pause);    return 0;}There is another much more beautiful solution for this problem comes from an unknown friend akash01:void printIlsRecur (char *str1, char *str2, char *iStr, int m, int n, int i){    // Base case: If all characters of str1 and str2 have been included in    // output string, then print the output string    if ( m==0 && n ==0 )    {        printf(%s\n, iStr) ;    }    // If some characters of str1 are left to be included, then include the     // first character from the remaining characters and recur for rest    if ( m != 0 )    {        iStr[i] = str1[0];        printIlsRecur (str1 + 1, str2, iStr, m-1, n, i+1);    }    // If some characters of str2 are left to be included, then include the     // first character from the remaining characters and recur for rest    if ( n != 0 )    {        iStr[i] = str2[0];        printIlsRecur (str1, str2+1, iStr, m, n-1, i+1);    }}
Print all interleavings of two given strings
c++;strings;recursion;combinatorics