Trace s = "catsand", wordDict = ["cat","cats","and"].
solve(0):
- "cat" matches s[0:3]. solve(3) → ["and"] → result: ["cat and"]
- "cats" matches s[0:4]. solve(4) → ["and"]? No, s[4:7]="and" but s[4:]="and" works. → result: ["cats and"]
Wait, let's be precise. s = "catsand" (length 7).
- Position 0: "cat" → solve(3). "cats" → solve(4).
- Position 3: "and" matches → solve(6). But length is 7, so solve(7).
- Position 4: "and" matches s[4:7] → solve(7).
- Position 7: base case, return [""].
Results: ["cat and", "cats and"].
Worst case sentences (exponential). Space: for all outputs.