Use memoized backtracking. At each position, try all dictionary words that match the prefix.
solve(i) returns all ways to segment s[i:]. For each word in dictionary that matches s[i:i+len(word)], prepend that word to all results from solve(i+len(word)).
Memoize to avoid recomputing. Base: at end of string, return one empty sentence.
This is DP + backtracking combined. DP tells you which positions are reachable; backtracking reconstructs all paths.