Return all valid word-break sentences
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
Given a string `s` and a dictionary of strings `wordDict`, insert spaces into `s` to form a sentence such that every token is in `wordDict`.
Return **all possible sentences** that can be formed. Words from the dictionary may be reused multiple times.
Constraints/notes:
- Output sentences should preserve the original character order.
- If no valid segmentation exists, return an empty list.
Quick Answer: This question evaluates skills in string processing, recursive search/backtracking, enumeration of all valid segmentations, and algorithmic complexity reasoning for generating multiple solutions.
