C program to print all interleaving of two strings

An interleaving can be formed using the characters present in the given two input strings.  But, the order of characters in each string needs to be maintained.

For example, str1 = "12" and str2 = "34".  Then the possible interleavings are as follows.
1234
1324
1342
3124
3142
3412

The length of each interleaving is equal to the sum of length of the given two input strings.  And the number of possible interleavings can be found using the below formula.

(m+n)Cm =  (m+n)! / m!((m + n) - m) !

Write a C program to print all interleaving of two strings.

  #include <stdio.h>
  #include <string.h>

  /* prints all possible interleavings of given two input strings */
  void interleave(char *str1, char *str2, char * output, int len) {
        if (*str1 == '\0' && *str1 == '\0') {
                /* prints the interleaving */
                if (*(output - len))
                        printf("%s\n", output - len);
        }

        /* interleaving manipulation */
        if (*str1 != '\0') {
                output[0] = str1[0];
                interleave(str1 + 1, str2, output + 1, len);
        }

        if (*str2 != '\0') {
                output[0] = str2[0];
                interleave(str1, str2 + 1, output + 1, len);
        }

        return;
  }

  int main() {

        int len;

        char str1[256], str2[256], output[512];

        /* get the first input string from the user */

        printf("Enter your first input string:");

        fgets(str1, 256, stdin);

        str1[strlen(str1) - 1] = '\0';

        /* get the second input string from the user */

        printf("Enter your second input string:");

        fgets(str2, 256, stdin);

        str2[strlen(str2) - 1] = '\0';

        /* length of each interleaving */

        len = strlen(str1) + strlen(str2);

        /* initializing output array */

        memset(output, '\0', sizeof(output));

        /* prints all possible interleavings */

        interleave(str1, str2, output, len);

        return 0;

  }

  Output:

  jp@jp-VirtualBox:~/$ ./a.out
  Enter your first input string:12
  Enter your second input string:34
  1234
  1324
  1342
  3124
  3142
  3412