We're given a string and a dictionary, and we need to find every way to split the string into a sequence of dictionary words. The related Word Break problem (LeetCode 139) asks only "can it be segmented?" and a boolean answer suffices. This problem asks for every valid segmentation, so we have to reconstruct the actual splits rather than just decide feasibility.

That difference matters. A boolean DP table records whether a suffix is segmentable, but it throws away how. To list every sentence, we need to enumerate all the paths through the string, which puts us in backtracking territory.

Three properties shape the approach. The same dictionary word can appear multiple times in one sentence. We need all valid sentences, not just one. And the string length is at most 20, so the number of valid sentences can itself be exponential, which means no algorithm can avoid producing exponential output in the worst case.

Framed differently, this is a search problem over the string. Each split corresponds to a path from the start to the end, where every step consumes a dictionary word that matches the next chunk of characters.

Key Constraints:

Intuition

Try every possible split. Start from position 0. At each position, try every prefix that matches a dictionary word. When one matches, add that word to the current sentence and continue from the position right after it. When the position reaches the end of the string, the current sentence is complete and valid.

This is backtracking. We build sentences word by word, and when no dictionary word matches the remaining string, we undo the last word and try a different one.

This terminates quickly because s.length is at most 20. The number of ways to split a 20-character string is bounded by 2^19, since each of the 19 gaps between characters is either a split point or not. The dictionary constraint rules out most of these splits, so the search visits far fewer paths in practice.

Algorithm

Visualization and Code

The brute force explores every prefix at every position, including positions whose remaining suffix cannot be decomposed at all. The next approach computes which positions can reach the end before searching, then skips the rest.

Intuition

The brute force spends time exploring paths that lead nowhere. The fix is to run a DP pass before backtracking. This pass computes, for each position, whether the suffix starting there can be segmented into dictionary words all the way to the end. It is the same recurrence used to decide feasibility in the basic Word Break problem. During backtracking, we then recurse only into positions whose suffix is known to be segmentable.

The DP array acts as a reachability map. A position marked false can never complete a valid sentence, so the search never enters it. This does not change the worst-case complexity, since the number of valid sentences can still be exponential, but it removes all the wasted work on suffixes that have no segmentation. On inputs like a long run of a characters with a dictionary that fails near the end, the brute force explores an exponential number of dead-end paths while the pruned version rejects the input after one DP pass.

Algorithm

Visualization and Code

The DP pruning eliminates dead-end branches, but when multiple paths converge at the same index, the search still recomputes the sentences for that index every time it arrives. The next approach caches the list of sentences for each starting index so each is computed once.

Intuition

The subproblems overlap. The set of all valid sentences from index i to the end depends only on i, not on the words chosen before reaching i. Whether the search arrived at index 3 via "cat" or via some other prefix, the sentences for the suffix s[3:] are identical.

So instead of backtracking, which re-explores those overlapping subproblems, we memoize. For each index i, compute the list of all valid sentences starting at i once, then store it. A later visit to the same index returns the cached list directly.

This turns "explore all paths" into "solve each suffix once." There are O(n) distinct starting indices, and each tries every dictionary word that fits in O(m * L) time. Assembling the final sentences still costs time proportional to the total output, which is unavoidable when the output itself can be exponential.

Algorithm

Visualization and Code