Print all sentences from a list of word lists
Problem
Given a list of word lists, print every sentence formed by picking exactly one word from each list, in list order.
Example 1
Input: [["you", "we"], ["have", "are"]] Output: "you have", "you are", "we have", "we are"
Also asked as: Recursively print all sentences that can be formed from list of word lists
Test cases
Case 1
Input: [["you","we"],["have","are"]] Expected (any order): ["you have","you are","we have","we are"]
Case 2
Input: [["hi"],["there","you"]] Expected (any order): ["hi there","hi you"]
Case 3
Input: [["a"]] Expected (any order): ["a"]
View solutionHide solution1 approach
1. Backtracking across rows
Time O(product of row sizes)Space O(rows)
Pick one word from row i, recurse to row i+1; a complete sentence is one word from every row.
function allSentences(lists) { const res = []; const bt = (row, acc) => { if (row === lists.length) { res.push(acc.join(' ')); return; } for (const w of lists[row]) bt(row + 1, [...acc, w]); }; bt(0, []); return res;}