Leetcode 140. Word Break II

Given a string s and a word dictionary, return all possible sentences formed by inserting spaces so every token is a dictionary word — i.e., enumerate all valid segmentations. The challenge is to generate all combinations efficiently by exploring prefixes and using memoization/DP to avoid exponential rework and prune impossible splits.