242. Print All Sentences from a List of Word Lists

You're given M lists of words, one list per position in a sentence. Print every sentence that can be formed by picking exactly one word from each list, in order. Generate them by trying the first list's words in the given order, and for each choice, recursively trying the next list's words in given order (standard nested left-to-right enumeration). Print each sentence as its chosen words space-separated, and separate different sentences with ' | ', in the order generated. Input: the first line is M; each of the next M lines starts with that list's word count followed by its words, space-separated.

Input: The first line contains the integer M. Each of the next M lines starts with that list's word count, followed by its words, space-separated. Output: Print every possible sentence (one word chosen from each list, in nested left-to-right order), each sentence's words space-separated, sentences separated by ' | '.

1 <= M <= 6, 1 <= words per list <= 6, 1 <= |each word| <= 20

Preserving the EXACT nested generation order (first list's words vary slowest, last list's words vary fastest) is an explicit requirement here - getting the recursion's iteration order right matters just as much as generating the correct combinations.

Given several lists of words (one list per sentence position), print every possible sentence formed by picking exactly one word from each list, in order. Brute force: This problem's very nature requires generating every combination - there's no way to avoid visiting all (product of each list's size) combinations, since the problem explicitly asks for every one of them, printed in a specific nested order. Optimised: The recursive 'choose one word from this list, then recurse into the remaining lists' approach generates each combination exactly once, in precisely the nested left-to-right order the problem requires - no wasted work, no need for a separate ordering step afterward.

Recurse position by position: maintain a shared buffer of chosen words so far; at position i, try each word in the i-th list in order, append it to the buffer, recurse to position i+1, and remove it afterward (backtrack) before trying the next word. When the recursion reaches position M, print the buffer as one complete sentence. Because the recursion naturally follows the "first list's words in order, then next list's words in order" structure the problem asks for, and only ever holds one in-progress sentence (of length at most M) on the stack, this is both the clearest expression of the enumeration and the leanest in memory. Time: O(M * total combinations) Space: O(M)

Treat each sentence as a number in a mixed-radix system where position i has "base" equal to the size of the i-th word list. Compute the total number of combinations as the product of all list sizes, then loop a counter from 0 up to that total minus one; for each counter value, repeatedly take it modulo the current list's size to get that position's word index and divide by that size to move to the next position, building the sentence directly from the decoded indices and printing it immediately. This produces every combination in the same left-to-right generation order without ever storing more than one sentence at a time. Time: O(M * total combinations) Space: O(1)

Start with a list containing one empty partial sentence. For each of the M word lists in turn, build a brand-new list where every existing partial sentence is combined with every word from the current list (string-concatenated), replacing the old list of partials with this larger one. After processing all M lists, the final list holds every complete sentence, which is then joined with ' | ' and printed. This works but keeps every intermediate partial sentence materialized in memory at each expansion step, which is wasteful compared to generating and discarding sentences one at a time. Time: O(M * total combinations) Space: O(M * total combinations)

1. Recurse position by position: at the first list, try each word in the given order. 2. For each choice, recursively try every word of the NEXT list, and so on, building up the sentence one word at a time. 3. When all positions have a chosen word, record the completed sentence; after all recursive branches finish, print them in the exact order generated.

Time: O(product of all list sizes * M), where M is the number of lists (positions) - since each of the combinations takes O(M) to build and print. Space: O(M) for the recursion depth (one level per list), plus O(product of all list sizes * M) if all sentences are stored before printing.

M = 1 (each word in the single list is its own sentence); the maximum M = 6 lists of 6 words each, producing 6^6 sentences, testing enumeration performance.

Be ready to connect this directly to 'Print All Permutations of a String' - the underlying recursive backtracking shape is identical, just with each recursive 'slot' having its own distinct choice set instead of sharing one shrinking pool of characters.