#### Miscellaneous

Problem
Given 2 strings, find all possible interleaved combination of the characters of the 2 strings.
Consider two strings ” AB ” & ” PQ “.
Possible interleaved combination are :-
ABPQ | APBQ | APQB | PABQ | PAQB | PQAB

Solution
This problem is similar to the balanced parenthesis problem discussed earlier.
There are two possible options of interleaving characters of two strings.
1 ) First character of the interleaved string is from first string str1. We will recursively consider all the characters of str1 and str2 to obtain possible interleaved combinations.
2 ) First character of the interleaved string is from second string str2. We will follow the same recursive technique. See the implementation below.

```#include<iostream>
using namespace std;

// print all possible interleaved combination of the characters of 2 strings
// start1 and start2 keeps track of the indices in str1[] & str2[] respectively
void printCombination(char str1[],char str2[],char str[],int size1,int size2,                                               int pos,int start1,int start2) {
if(pos == size1+size2) {
str[pos] = 0; // null terminate the string
cout<<str<<endl;
}
if(start1 < size1) {
str[pos] = str1[start1];
printCombination(str1,str2,str,size1,size2,pos+1,start1+1,start2);
}
if(start2 < size2) {
str[pos] = str2[start2];
printCombination(str1,str2,str,size1,size2,pos+1,start1,start2+1);
}
}

// wrapper function
void interleave(char str1[],char str2[],int size1,int size2) {
// character array to store the interleaved combination
char str[size1*size2];
int pos = 0; // index of 'str'
printCombination(str1,str2,str,size1,size2,pos,0,0);
}

// main
int main() {
char str1[] = {'A','B','P'};
char str2[] = {'C','D','Q'};
cout<<"\nPossible interleaved combination :-\n";
interleave(str1,str2,sizeof(str1),sizeof(str2));
cout<<endl;
return 0;
}```

Back