Basic decomposition
Input
s = 'catsanddog', word_dict = ['cat', 'cats', 'and', 'sand', 'dog']
Output
['cat sand dog', 'cats and dog']
Two ways to split 'catsanddog': 'cat sand dog' and 'cats and dog'.
Full lesson preview
Find all word breaks
Given a string and a dictionary of words, return all possible space-separated sentences that form the string using dictionary words.
Python practice15 minRecursion & BacktrackingIntermediateLast updated March 27, 2026
Problem statement
Given a non-empty string s and a dictionary of words word_dict, find all possible sentences where spaces are inserted into s such that every segment is a valid word from word_dict. Return the list of sentences sorted in lexicographical order. Each dictionary word may be used multiple times. Use recursion (with memoization) to build solutions efficiently.
Task
Practice recursion with memoization to explore all decompositions of a string into dictionary words (word break II).
Examples
Input format
A string s and a list of strings word_dict.
Output format
A list of sentences (strings). Each sentence is a space-separated sequence of dictionary words. The returned list is sorted lexicographically.
Constraints
- 1 <= len(s) <= 30
- word_dict contains 1..50 words
- All words contain only lowercase letters
- Use recursion; optimize with memoization to avoid exponential blowup
Samples
Sample 1
Input
s = 'pineapplepenapple', word_dict = ['apple','pen','applepen','pine','pineapple']
Output
['pine apple pen apple', 'pine applepen apple', 'pineapple pen apple']
There are three valid sentences; the returned list is lexicographically sorted.