Strings: Recursively print all sentences that can be formed from list of word lists

Problem Statement:

You are given list of words, you need to print all the combinations of phrases that can be formed by picking one word from each list.

Example

s[][] = {{“I”, “You”}, {“love”},{“programming”}}

OUTPUT
“I love programing”
“You love programming”

Solution

We need to take the idea of depth first traversal.

We start from every word from the first lest and then perform recursion on remaining lists.

Solution in C++

#include <algorithm>  
//visit www.ProDeveloperTutorial.com for 450+ solved questions  
#include <iostream>    
#include <string>
#include <queue>
#include <vector>
#include <stack> 

using namespace std;
  
#define R 3
#define C 3
 
void display_util(string arr[R][C], int m, int n, string result[R])
{
    result[m] = arr[m][n];
 
    // if it is the last word, then print
    if (m==R-1)
    {
        for (int i=0; i<R; i++)
        {
           cout << result[i] << " ";
        }
        cout << endl;
        return;
    }
   
    // perform recursion for next row.
    for (int i=0; i<C; i++)
    {
       if (arr[m+1][i] != "")
       {
          display_util(arr, m+1, i, result);
       }
    }
}
 
void display_all_sentences(string arr[R][C])
{
   string result[R];
 
   for (int i=0; i<C; i++)
   {
     if (arr[0][i] != "")
     {
        display_util(arr, 0, i, result);
     }
   }
}
 
int main()
{
   string arr[R][C]  = {{"I", "You"}, {"love", "like"},{"programming"}};
 
   display_all_sentences(arr);
 
   return 0;
}

Output:

I love programming
I like programming
You love programming
You like programming