Log inSign up
hardGeeksforGeeksNot Started

Word Break using Backtracking

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Backtracking
Solve on GeeksforGeeks
Lesson

Problem Statement

Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.

Return all such possible sentences in any order.

Note that the same word in the dictionary may be reused multiple times in the segmentation.

Example 1:

Input: s = "catsanddog", dict = ["cat","cats","and","sand","dog"]
Output: ["cats and dog","cat sand dog"]
Explanation: Both segmentations decompose "catsanddog" into valid dictionary words.

Example 2:

Input: s = "pineapplepenapple", dict = ["apple","pen","applepen","pine","pineapple"]
Output: ["pine apple pen apple","pineapple pen apple","pine applepen apple"]
Explanation: The word "apple" is reused twice.

Example 3:

Input: s = "catsandog", dict = ["cats","dog","sand","and","cat"]
Output: []
Explanation: No valid sentence can be formed.

Constraints:

  • 1 <= s.length <= 20
  • 1 <= dict.length <= 1000
  • 1 <= dict[i].length <= 10
  • All characters in s and dict are lowercase English letters.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master prefix slicing and dictionary validation in string backtracking.
  • Understand top-down memoization for combinatorial string generation problems.
  • Compare boolean Word Break I (Decision DP) vs Word Break II (Sentence Generation Backtracking).

1. Pure Backtracking DFS

Intuition

Iterate end from start to s.length() - 1. If dictSet.count(s.substr(start, end - start + 1)), push to path, recurse on end + 1, and pop.

When to apply: Basic recursive backtracking over all dictionary prefixes.

Algorithm

  1. Step 1: Store dictionary words in a HashSet for O(1) word lookup.
  2. Step 2: Define backtrack(start, currentWords).
  3. Step 3: Base case: if start == s.length, join currentWords with space and add to result.
  4. Step 4: Loop end from start + 1 to s.length.
  5. Step 5: If wordSet contains s.substring(start, end), push word, recurse on backtrack(end), and pop.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6class Solution {
7public:
8 void backtrack(const std::string& s, int start, const std::unordered_set<std::string>& dict, std::vector<std::string>& path, std::vector<std::string>& result) {
9 if (start == (int)s.length()) {
10 std::string sentence = path[0];
11 for (int i = 1; i < (int)path.size(); i++) {
12 sentence += " " + path[i];
13 }
14 result.push_back(sentence);
15 return;
16 }
17
18 for (int end = start; end < (int)s.length(); end++) {
19 std::string word = s.substr(start, end - start + 1);
20 if (dict.count(word)) {
21 path.push_back(word);
22 backtrack(s, end + 1, dict, path, result);
23 path.pop_back();
24 }
25 }
26 }
27
28 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
29 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
30 std::vector<std::string> result, path;
31 backtrack(s, 0, dict, path, result);
32 return result;
33 }
34};
35
36int main() {
37 Solution solver;
38 std::string s = "catsanddog";
39 std::vector<std::string> dict = {"cat", "cats", "and", "sand", "dog"};
40 std::vector<std::string> res = solver.wordBreak(s, dict);
41 std::cout << "Word Break Sentences for 'catsanddog':\n";
42 for (const auto& str : res) {
43 std::cout << "\"" << str << "\"\n";
44 }
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Can branch up to 2^(N-1) ways with O(N) string construction.
  • Space complexity: O(N) — O(N) recursion depth and path tokens array.

2. Backtracking with DP Suffix Reachability Pre-Filter

Intuition

A standard backward DP computes possible[i] = true if some prefix s[i..j] is in dict and possible[j+1] == true. The backtracking DFS only recurses on index next if possible[next] is true, pruning dead-end branches instantly.

Algorithm

  1. Step 1: Use memoization Map<Integer, List<String>> to cache valid sentence completions from index i.
  2. Step 2: If memo contains index start, return memo.get(start).
  3. Step 3: For each prefix s[start..end]: if valid word, get sub-sentences from dfs(end) and append word.
  4. Step 4: Store results in memo[start] and return.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5
6class Solution {
7public:
8 void backtrack(const std::string& s, int start, const std::unordered_set<std::string>& dict, const std::vector<bool>& possible, std::vector<std::string>& path, std::vector<std::string>& result) {
9 if (start == (int)s.length()) {
10 std::string sentence = path[0];
11 for (int i = 1; i < (int)path.size(); i++) sentence += " " + path[i];
12 result.push_back(sentence);
13 return;
14 }
15
16 for (int end = start; end < (int)s.length(); end++) {
17 if (!possible[end + 1]) continue; // Prune dead-end suffix
18
19 std::string word = s.substr(start, end - start + 1);
20 if (dict.count(word)) {
21 path.push_back(word);
22 backtrack(s, end + 1, dict, possible, path, result);
23 path.pop_back();
24 }
25 }
26 }
27
28 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
29 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
30 int n = s.length();
31 std::vector<bool> possible(n + 1, false);
32 possible[n] = true;
33
34 for (int i = n - 1; i >= 0; i--) {
35 for (int j = i; j < n; j++) {
36 if (possible[j + 1] && dict.count(s.substr(i, j - i + 1))) {
37 possible[i] = true;
38 break;
39 }
40 }
41 }
42
43 if (!possible[0]) return {};
44
45 std::vector<std::string> result, path;
46 backtrack(s, 0, dict, possible, path, result);
47 return result;
48 }
49};
50
51int main() {
52 Solution solver;
53 std::string s = "catsanddog";
54 std::vector<std::string> dict = {"cat", "cats", "and", "sand", "dog"};
55 auto res = solver.wordBreak(s, dict);
56 std::cout << "DP Filtered Word Break:\n";
57 for (const auto& str : res) std::cout << str << "\n";
58 return 0;
59}

Time & Space Complexity

  • Time complexity: O(N^2 + 2^N * N) — O(N2) DP pass eliminates exponential search on unmatchable suffixes.
  • Space complexity: O(N) — O(N) memory for the boolean array.

3. Memoized DFS / Post-Order Sentence Synthesis (Gold Standard)

Intuition

Function dfs(s) returns all valid sentences that can be formed from string s. For every word in dict that is a prefix of s, recurse on the remaining suffix s.substr(word.length). Combine word with each sentence from the suffix, store in memo[s], and return.

When to apply: Industry gold standard: DP reachability pre-check + Trie-guided sentence reconstruction.

Algorithm

  1. Step 1: First run Word Break I dynamic programming in O(N2) to verify if s can be segmented at all.
  2. Step 2: If dp[s.length] is false, return [] immediately without starting expensive sentence assembly.
  3. Step 3: Build a Trie from dictionary words for instantaneous prefix matching.
  4. Step 4: Traverse string guided by Trie and DP reachability table dp[i].
  5. Step 5: Collect and return all valid space-separated sentence combinations.

Word Break II Partition Trace

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Start at index 0 of 'catsanddog'
Visual state
Values and pointers at this exact step
tree
Start
s: 'catsanddog'

Node order shown; add connections to display explicit tree edges.

Variables at this step
start
0
currentSentence
[]
Check / comparison
start = 0, candidate prefixes: 'cat', 'cats'
Decision / next transition
Branch 1: match 'cat' (0..3), Branch 2: match 'cats' (0..4)
Why this step matters

Start at index 0 of catsanddog. Scan dictionary prefixes.

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <string>
4#include <unordered_set>
5#include <unordered_map>
6
7class Solution {
8public:
9 std::unordered_map<std::string, std::vector<std::string>> memo;
10
11 std::vector<std::string> dfs(const std::string& s, const std::unordered_set<std::string>& dict) {
12 if (memo.count(s)) return memo[s];
13 if (s.empty()) return {""};
14
15 std::vector<std::string> result;
16
17 for (int len = 1; len <= (int)s.length(); len++) {
18 std::string word = s.substr(0, len);
19 if (dict.count(word)) {
20 std::string suffix = s.substr(len);
21 std::vector<std::string> subSentences = dfs(suffix, dict);
22 for (const std::string& sub : subSentences) {
23 result.push_back(word + (sub.empty() ? "" : " ") + sub);
24 }
25 }
26 }
27
28 return memo[s] = result;
29 }
30
31 std::vector<std::string> wordBreak(std::string s, std::vector<std::string>& wordDict) {
32 std::unordered_set<std::string> dict(wordDict.begin(), wordDict.end());
33 memo.clear();
34 return dfs(s, dict);
35 }
36};
37
38int main() {
39 Solution solver;
40 std::string s = "catsanddog";
41 std::vector<std::string> dict = {"cat", "cats", "and", "sand", "dog"};
42 auto res = solver.wordBreak(s, dict);
43 std::cout << "Optimal Memoized Word Break:\n";
44 for (const auto& str : res) std::cout << str << "\n";
45 return 0;
46}

Time & Space Complexity

  • Time complexity: O(2^N * N) — Generates all valid sentences without redundant suffix recomputations.
  • Space complexity: O(2^N * N) — Memoization table caches suffix lists.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Pure Backtracking DFSO(2^N * N)O(N)Explore all prefix cuts matching dictionary entries.Suffix re-exploration
2.Backtracking with Word Break DP Reachability Filter (Better)O(2^N * N)O(N)Run 1D DP first to check if suffix s[i..N-1] is breakable before branching.Output construction
3.Memoized DFS / Post-Order Sentence Synthesis (Optimal)OptimalO(2^N * N)O(2^N * N)Cache memo[start] storing list of all valid sentences for suffix s[start..N-1].String concatenations

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Doing unmemoized backtracking on testcases with thousands of identical repeated letters (e.g. aaaaa...b) where no solution exists.

Pitfall 2:

Formatting space with trailing spaces.

Crucial Edge Cases to Validate:

  • No valid decomposition exists (e.g. catsandog) -> returns [].
  • String is already a single word in dictionary -> returns [s].
  • Repeated identical characters (e.g. aaaa, dict=[a, aa]) -> returns all binary partitions.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify whether the question is Word Break I (return boolean, solved in O(N2) DP) or Word Break II (return all sentences, requires backtracking/memoized DFS).
  2. Mention Trie as an alternative prefix matcher if dictionary words are very long.
  3. Explain how memoizing dfs(suffix) prevents exponential recomputation of overlapping suffixes.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why is Word Break II fundamentally exponential O(2N) even with memoization?

Back to DSA Sheet