Word Break II | Backtracking

geeksforgeeks.org

Problem Statement

Given a string s and a dictionary wordDict, return all possible sentences where:

• Every word exists in the dictionary.
• Spaces can be inserted anywhere valid.

Return all valid sentences.

---

Brute Force Intuition

Try every possible cut in the string.

For every substring:

Check if it exists in dictionary

If yes:

Take it
Recursively solve remaining string

If no:

Skip it

This naturally forms a recursion tree.

Complexity

• Time Complexity: Exponential
• Space Complexity: O(N)

---

Moving Towards the Optimal Approach

Instead of generating every partition first:

At every index:

Try all possible substrings

Only continue if:

substring ∈ dictionary

This prunes many invalid paths.

Using a HashSet makes word lookup O(1).

---

Pattern Recognition

Whenever you see:

• String partitioning
• Dictionary lookup
• Return all valid ways

Think:

Backtracking + HashSet

---

Key Observation

Example:

s = "catsanddog"

dict = ["cat","cats","and","sand","dog"]

At index 0:

"c"      ❌
"ca"     ❌
"cat"    ✅
"cats"   ✅

Only valid words create recursive branches.

---

Recursive Tree

catsanddog

          ""
        /    \
     cat     cats
      |        |
    sand      and
      |        |
     dog      dog
      |        |
 cat sand dog
 cats and dog

---

Optimal Java Solution

import java.util.*;

class Solution {

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

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

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

        solve(0, s, dict, "", ans);

        return ans;
    }

    private void solve(int index,
                       String s,
                       Set<String> dict,
                       String sentence,
                       List<String> ans) {

        if (index == s.length()) {

            ans.add(sentence.trim());

            return;
        }

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

            String word =
                s.substring(index, end + 1);

            if (dict.contains(word)) {

                solve(end + 1,
                      s,
                      dict,
                      sentence + word + " ",
                      ans);
            }
        }
    }
}

---

Dry Run

Input

s = "catsanddog"

dict =
["cat","cats","and","sand","dog"]

---

Path 1

cat
 ↓
sand
 ↓
dog

Sentence:

"cat sand dog"

---

Path 2

cats
 ↓
and
 ↓
dog

Sentence:

"cats and dog"

---

Output

[
 "cat sand dog",
 "cats and dog"
]

---

Why Backtracking Works?

At every index:

Try every possible word

If the word exists in dictionary:

Choose
Explore
Backtrack

Eventually all valid sentence combinations are generated.

---

Optimization (Interview Follow-up)

The same suffix may be solved repeatedly.

Example:

dog

can be reached through multiple paths.

Use:

HashMap<String, List<String>>

for memoization.

This converts the solution into:

Backtracking + DP

and significantly improves performance.

---

Complexity Analysis

Metric	Complexity
Time Complexity	Exponential
Space Complexity	O(N)

Without memoization, many suffixes are recomputed.

---

Interview One-Liner

At every index, try all possible substrings. If the substring exists in the dictionary, recursively generate sentences from the remaining string and append the current word.

---

Pattern Learned

String
+
Dictionary
+
All Valid Partitions

=> Backtracking

Similar Problems

• Word Break II
• Palindrome Partitioning
• Restore IP Addresses
• Expression Add Operators
• Letter Case Permutation

---

Memory Trick

Subsets
→ Pick / Not Pick

Palindrome Partitioning
→ Try Every Cut

Word Break II
→ Try Every Word

Mental Model

Current Index
      ↓
Try Every Substring
      ↓
Word Exists ?
      ↓
Take It
      ↓
Recurse

Whenever you hear:

"Return all possible sentences"

your brain should immediately think:

Backtracking + Dictionary Lookup + Try Every Cut 🚀