Branches whose remaining suffix cannot finish. It cannot discard different successful prefixes merely because they meet at the same suffix.

Use a trie to find word-end edges between boundaries. While filling suffix feasibility backward, retain only edges leading to a feasible suffix. Then backtrack through this pruned DAG, appending a word and undoing it after the recursive call. Every root-to-end boundary path produces one sentence. The DP never commits to only one successful edge. This shares discovery and rejects dead ends while preserving all requested outputs.

What the function promises: s is nonempty and dictionary words are nonempty and reusable. Return all distinct sentences in any order. The helper returns [] for empty s. The original problem bounds s to length 20; the enumeration recursion is intended for that small-input contract.

def build_trie(words):
    root = {}
    for word in set(words):
        if not word:
            raise ValueError("Dictionary words must be nonempty")
        node = root
        for letter in word:
            node = node.setdefault(letter, {})
        node[None] = True
    return root

def all_sentences(s, words):
    if not s:
        return []
    root = build_trie(words)
    n = len(s)
    can = [False] * (n + 1)
    can[n] = True
    following = [[] for _ in range(n)]
    for i in range(n - 1, -1, -1):
        node = root
        for j in range(i, n):
            if s[j] not in node:
                break
            node = node[s[j]]
            if None in node and can[j + 1]:
                following[i].append(j + 1)
                can[i] = True
    answer, path = [], []

    def emit(i):
        if i == n:
            answer.append(" ".join(path))
            return
        for end in following[i]:
            path.append(s[i:end])
            emit(end)
            path.pop()

    emit(0)
    return answer

assert sorted(all_sentences("cars", ["car", "ca", "rs"])) == ["ca rs"]
assert len(all_sentences("aaaa", ["a", "aa"])) == 5
assert all_sentences("cars", ["car"]) == []
assert all_sentences("a", ["a", "a"]) == ["a"]

Work and storage: Let B be the total characters across returned sentences. Trie/feasibility preparation takes expected O(W+nL) time and O(W+nL) space. Enumeration and string construction add O(B) output-sensitive work and storage, with O(n) recursion depth. B can be exponential in n.

When to recognize it: First mark suffixes that can finish. Then enumerate only word choices leading to those suffixes.

Check before applying it: A yes/no cache cannot replace the actual sentences. There may be exponentially many valid outputs.

No. Use a count per suffix, summing counts across word-end edges. That avoids enumerating each sentence, although large integer counts may themselves require more than constant-time arithmetic.