Print all interleavings of two given strings
Your algorithm is correct, as you explained.  However, I didn't find the code easy to understand.

Staying within the spirit of your solution, I've cleaned it up a bit:


Renamed s2 → s1 (because s2 coming first is confusing), result → s2.
Renamed depth → i1, start → i2 to emphasize their relationship with s1 and s2.
Swapped the order of the last two parameters for parallelism.
Provided defaults for the last two parameters to make main() prettier.
Eliminated the variable i, because using i2 directly is clearer.
Used an early return to reduce a level of indentation.


Simultaneously tracking all of those substitutions is tricky, but here is the result:

void interleaving(const string&amp; s1, string s2, int i1=0, int i2=0)
{
    if (i1 == s1.size())
    {
        cout &lt;&lt; s2 &lt;&lt; endl;
        return;
    }

    // Transfer the first character of s1 into s2
    // anywhere after the last previously inserted
    // character from s1.
    for ( ; i2 &lt;= s2.size(); i2++)
    {
        s2.insert(i2, 1, s1[i1]);
        interleaving(s1, s2, i1 + 1, i2 + 1);
        s2.erase(i2, 1);        // Undo the insert() above
    }
}


Since passing the second parameter by value would cause it to be copied unnecessarily on each recursive call, you might want to change it to be passed by reference instead.

static void interleaving_helper(const string&amp; s1, string &amp;s2, int i1, int i2)
{
    if (i1 == s1.size())
    {
        cout &lt;&lt; s2 &lt;&lt; endl;
        return;
    }

    for ( ; i2 &lt;= s2.size(); i2++)
    {
        s2.insert(i2, 1, s1[i1]);
        interleaving_helper(s1, s2, i1 + 1, i2 + 1);
        s2.erase(i2, 1);        // Undo the insert above
    }
}

void interleaving(const string&amp; s1, string s2, int i1=0, int i2=0)
{
    interleaving_helper(s1, s2, i1, i2);
}