Print all sentences from a list of word lists

Medium

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"]

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}