You are given a string s and a list of words wordDict.
You must return all possible sentences where s can be segmented such that each segment is a word in the dictionary.

Unlike Word Break I (Problem 139), where you return true/false, here you must return all valid combinations.

---

Understanding the Problem

Example:

s = “catsanddog”
wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]

Valid sentences:

“cats and dog”
“cat sand dog”

Example:

s = “pineapplepenapple”
wordDict = [“apple”,”pen”,”applepen”,”pine”,”pineapple”]

Valid sentences:

“pine apple pen apple”
“pineapple pen apple”
“pine applepen apple”

The string can have many possible valid segmentations.
This makes it a DFS + memoization problem, NOT simple DP.

---

Approach (Explained in Simple Language)

The best solution uses recursion with memoization.

Step 1: Use DFS to explore all possible splits

Start from index 0 and try:

If s starts with some word w from wordDict:
Recurse on the remaining substring.

Step 2: Store computed results in memo

Since substrings repeat often, memoization ensures each substring is solved once.

memo.get(start) = list of all sentences beginning at index start

Step 3: Build sentences

When a word is found and the recursive call returns sub-sentences, append:

word + ” ” + subSentence

If the word consumes the entire string, the sentence is exactly that word.

Step 4: Return all constructed valid sentences

---

Key Insight

Without memoization, recursion would explode exponentially.
Memo ensures each substring is processed once.

---

Java Code

import java.util.*;

public class WordBreakII {

    public List<String> wordBreak(String s, List<String> wordDict) {

        Set<String> dict = new HashSet<>(wordDict);

        Map<Integer, List<String>> memo = new HashMap<>();

        return dfs(0, s, dict, memo);
    }

    private List<String> dfs(int start, String s, Set<String> dict,
                             Map<Integer, List<String>> memo) {

        if (memo.containsKey(start)) {
            return memo.get(start);
        }

        List<String> result = new ArrayList<>();

        if (start == s.length()) {
            result.add("");
            return result;
        }

        for (int end = start + 1; end <= s.length(); end++) {

            String word = s.substring(start, end);

            if (dict.contains(word)) {

                List<String> subSentences = dfs(end, s, dict, memo);

                for (String sub : subSentences) {
                    if (sub.isEmpty()) {
                        result.add(word);
                    } else {
                        result.add(word + " " + sub);
                    }
                }
            }
        }

        memo.put(start, result);
        return result;
    }

    public static void main(String[] args) {
        WordBreakII sol = new WordBreakII();
        System.out.println(sol.wordBreak("catsanddog",
                Arrays.asList("cat","cats","and","sand","dog")));
    }
}

---

Dry Run

Input:

s = “catsanddog”
wordDict = [“cat”,”cats”,”and”,”sand”,”dog”]

Start DFS from index 0.

---

DFS(0): substring “catsanddog”

Try possible words:

Check “c”, “ca”: not in dict

Check “cat” → valid

Call DFS(3)

Check “cats” → valid

Call DFS(4)

Continue…

---

DFS(3): substring “sanddog”

Try words starting at index 3:

“s”, “sa”: no
“sand” → valid
Call DFS(7)

---

DFS(4): substring “anddog”

Try:

“a”, “an”: no
“and” → valid
Call DFS(7)

---

DFS(7): substring “dog”

Try:

“d”, “do”: no
“dog” → valid
Call DFS(10)

---

DFS(10): start == s.length()

Return [“”]

---

Backtracking assembly

At DFS(7):

word = “dog”
subSentences = [“”]

So DFS(7) → [“dog”]

---

At DFS(3):

word = “sand”
subSentences = [“dog”]

Add:

“sand dog”

So DFS(3) → [“sand dog”]

---

At DFS(4):

word = “and”
subSentences = [“dog”]

Add:

“and dog”

So DFS(4) → [“and dog”]

---

At DFS(0):

We have two valid first words:

Case 1: “cat” + DFS(3)

DFS(3) = [“sand dog”]
So add:

“cat sand dog”

Case 2: “cats” + DFS(4)

DFS(4) = [“and dog”]
So add:

“cats and dog”

---

Final Answer

[“cat sand dog”,
“cats and dog”]

---

Why This Approach Works

The recursive DFS explores all splits, while memoization prevents repeated work.

Complexity without memo: exponential
Complexity with memo: manageable, roughly O(n³)

Memoization ensures each starting index is solved once.