Construction and Exploration

What is this?

Choose, recurse, undo. Every problem here uses that same skeleton, and every one is decided by something else: what you know before the recursion starts. A validity rule that kills a segment immediately. A prefix map that offers only words which can legally follow. A union-find that groups synonyms so thoroughly there is barely a search left. And one problem where you cannot see the input at all.

💡 Fun fact: Word Squares has a constraint most people miss on the first read — the square must read the same across and down, which means that once k rows are placed, row k is completely determined in its first k characters: they are the k-th letters of the rows above. So the candidate list is not "all words", it is "all words with this exact prefix". Precomputing a prefix → words map turns an intractable search into one that finishes instantly, and the map is four lines.

🔓 The 4 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

The one-line idea: write the recursion in thirty seconds, then spend the rest of your time on the cheapest test that proves a branch is dead — that test is the solution.

1. Reject per segment, not per candidate

def bt(i, parts):
    if len(parts) == 4:
        if i == len(s): out.append(".".join(parts))
        return
    for L in (1, 2, 3):
        if i + L > len(s): break
        seg = s[i:i+L]
        if (seg[0] == '0' and L > 1) or int(seg) > 255: continue   # dead now
        bt(i + L, parts + [seg])

Both rejections happen the instant a segment is formed, so no branch survives to depth four just to be discarded. The leading-zero rule is the one people forget: "0" is valid, "01" is not, and it costs a single clause.

The tree has at most three branches per level over four levels, so this is O(1) regardless of input length — worth saying, because it sounds wrong and is not.

2. Precompute the legal candidates

pref = defaultdict(list)
for w in words:
    for i in range(n + 1):
        pref[w[:i]].append(w)             # every prefix maps to the words holding it

def bt(square):
    if len(square) == n: out.append(square[:]); return
    k = len(square)
    p = "".join(w[k] for w in square)     # column k of the rows already placed
    for cand in pref[p]:                  # only words that can legally follow
        square.append(cand); bt(square); square.pop()

The line that carries everything is p: reading down column k of the placed rows gives the prefix row k must start with. Without the map you would filter the whole word list at every node; with it, you index straight to the survivors.

A trie is the textbook alternative and is asymptotically the same. The hash map is shorter to write and easier to explain under time pressure — mention both, pick one, move on.

3. Group first, and the search dissolves

Synonym pairs are transitive — if a ~ b and b ~ c then all three are interchangeable — so union-find gives the true equivalence classes. After that, each word in the sentence contributes either one option or its whole sorted group, and the answer is their product in order. Sorting each group is what makes the output lexicographic without a final sort of the (potentially enormous) result.

4. Explore what you cannot see

def bt(r, c, d):
    clean(); seen.add((r, c))
    for k in range(4):
        nd = (d + k) % 4
        nr, nc = r + dr[nd], c + dc[nd]
        if (nr, nc) not in seen and move():
            bt(nr, nc, nd)
            go_back()                     # turnRight ×2, move, turnRight ×2
        turnRight()

Coordinates are tracked relative to the start because there is no origin to ask about. move() returning false means a wall, which is how the room is discovered. And the undo is physical: turn around, move one, turn around again — restoring both position and heading, since a robot that returns facing the wrong way corrupts every subsequent direction.

5. A 30-second worked example (IP addresses)

s = "101023"

"1" · "0" · "10" · "23"        ✓   1.0.10.23
"1" · "0" · "102" · "3"        ✓   1.0.102.3
"10" · "1" · "0" · "23"        ✓   10.1.0.23
"10" · "10" · "2" · "3"        ✓   10.10.2.3
"101" · "0" · "2" · "3"        ✓   101.0.2.3

pruned immediately:
"1" · "01" · …                 ✗   leading zero
"10" · "10" · "23" · ""        ✗   fourth segment empty

Five valid addresses. Note "1" · "01" dies at depth two — it is never extended, which is the whole point. A version that assembles all four segments first and validates at the end explores several times as many nodes for the same answer.

6. Where you'll actually meet this

• Network tooling. Parsing and validating address strings under strict format rules.
• Robot vacuums and coverage. Blind exploration with relative odometry is the real algorithm, not a metaphor.
• Crossword and puzzle construction. Word squares are constraint satisfaction at small scale.
• Search query expansion. Expanding a phrase across synonym groups is the sentence problem exactly.
• Configuration solvers. Choose–recurse–undo with early rejection is how package and build solvers explore.

7. Problems in this chapter

▶ Restore IP Addresses

Every valid IP address formable from a digit string. Reject a segment the moment it exceeds 255 or carries a leading zero.
Pattern: backtracking with per-segment validation. Target: O(1) — the tree is bounded at 3⁴.

▶ Word Squares

All squares reading identically across and down. Build a prefix → words map, then place rows against the prefix the placed columns dictate.
Pattern: backtracking + precomputed candidates. Target: O(n · 26^L) worst case, far less in practice.

▶ Robot Room Cleaner

Clean an unknown room through a move API. Track relative coordinates, mark visited, and undo each move with a physical go-back routine.
Pattern: blind DFS with state restoration. Target: O(cells) time and space.

▶ Synonymous Sentences

All sentences formed by substituting synonyms, in lexicographic order. Union-find the synonym pairs, sort each group, then take the ordered product.
Pattern: union-find + enumeration. Target: output-bound.

8. Common pitfalls 🚫

• Validating only at the leaf. Rejecting a segment on creation is the entire optimisation.
• Allowing leading zeros. "0" is a valid segment, "01" is not.
• Filtering the whole word list at each node instead of indexing a prefix map.
• Forgetting that word squares must read both ways, which is what determines the required prefix.
• Restoring position but not heading in the robot's go-back routine.
• Treating synonyms as pairs rather than as classes. The relation is transitive.
• Sorting the final result in the sentence problem, when sorting each small group beforehand is both cheaper and sufficient.

9. Key takeaways

1. The recursion is boilerplate. The pruning is the algorithm.
2. Reject at the earliest provable death, not at the leaf.
3. A prefix map converts "try everything" into "try what can work" — and it is four lines.
4. Undo is not always an assignment. Sometimes it is four API calls, and both position and heading must return.
5. Preprocessing can remove the search. Union-find turns one of these into a product.
6. A bounded tree means O(1) — say it, even when it sounds wrong.
7. Why interviewers like it: everyone writes the same recursion, so the pruning is the only thing that distinguishes answers.

Order: Restore IP Addresses → Word Squares → Robot Room Cleaner → Synonymous Sentences.