Word Break II | Backtracking

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

Enter fullscreen mode Exit fullscreen mode

If yes:

Take it
Recursively solve remaining string

Enter fullscreen mode Exit fullscreen mode

If no:

Skip it

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Only continue if:

substring ∈ dictionary

Enter fullscreen mode Exit fullscreen mode

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"]

Enter fullscreen mode Exit fullscreen mode

At index 0:

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

Enter fullscreen mode Exit fullscreen mode

Only valid words create recursive branches.

Recursive Tree

catsanddog

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

Enter fullscreen mode Exit fullscreen mode

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);
            }
        }
    }
}

Enter fullscreen mode Exit fullscreen mode

Dry Run

Input

s = "catsanddog"

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

Enter fullscreen mode Exit fullscreen mode

Path 1

cat
 ↓
sand
 ↓
dog

Enter fullscreen mode Exit fullscreen mode

Sentence:

"cat sand dog"

Enter fullscreen mode Exit fullscreen mode

Path 2

cats
 ↓
and
 ↓
dog

Enter fullscreen mode Exit fullscreen mode

Sentence:

"cats and dog"

Enter fullscreen mode Exit fullscreen mode

Output

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

Enter fullscreen mode Exit fullscreen mode

Why Backtracking Works?

At every index:

Try every possible word

Enter fullscreen mode Exit fullscreen mode

If the word exists in dictionary:

Choose
Explore
Backtrack

Enter fullscreen mode Exit fullscreen mode

Eventually all valid sentence combinations are generated.

Optimization (Interview Follow-up)

The same suffix may be solved repeatedly.

Example:

dog

Enter fullscreen mode Exit fullscreen mode

can be reached through multiple paths.

Use:

HashMap<String, List<String>>

Enter fullscreen mode Exit fullscreen mode

for memoization.

This converts the solution into:

Backtracking + DP

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

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

Enter fullscreen mode Exit fullscreen mode

Mental Model

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

Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

“Return all possible sentences”

your brain should immediately think:

Backtracking + Dictionary Lookup + Try Every Cut 🚀