Backtracking Partition Enumeration

Description

This skill is about splitting a string into pieces that each follow a rule: every piece a palindrome, every piece a dictionary word, every piece a valid IP octet. The task is to list every way of doing it. The pieces must cover the string in order, so the only decision at each step is where the next piece ends. Backtracking over that one decision lists every valid partition. Checking each piece as soon as it's cut throws away doomed splits early.

We'll go from simple to more technical:

1. The pattern: try every end for the next piece, recurse on the rest, and undo the choice.
2. A second flavor: a fixed number of pieces (restoring IP addresses).
3. Where segmentation shows up in production (word splitting, parsing).
4. What breaks it: late checks, a missing undo, repeated checks, and format rules.

The approach

void backtrack(String s, int start, List<String> current, List<List<String>> result) {
    if (start == s.length()) {
        result.add(new ArrayList<>(current));   // every piece so far passed - a complete partition
        return;
    }
    for (int end = start + 1; end <= s.length(); end++) {
        String piece = s.substring(start, end);
        if (isValid(piece)) {                    // only continue from valid pieces
            current.add(piece);
            backtrack(s, end, current, result);
            current.remove(current.size() - 1);  // un-choose, then try a longer piece
        }
    }
}

def backtrack(s: str, start: int, current: list[str], result: list[list[str]]) -> None:
    if start == len(s):
        result.append(current[:])               # every piece so far passed - a complete partition
        return
    for end in range(start + 1, len(s) + 1):
        piece = s[start:end]
        if is_valid(piece):                     # only continue from valid pieces
            current.append(piece)
            backtrack(s, end, current, result)
            current.pop()                       # un-choose, then try a longer piece

This is the choose-explore-un-choose loop from combinations, with a different choice: instead of "which element next", it's "where does this piece end". Reaching the end of the string means every piece along the way was valid, so the current list is a complete answer. Checking validity at the cut, not at the end, prunes every branch that starts with an invalid piece.

A second flavor: a fixed number of pieces

Restoring IP addresses splits a digit string into exactly four octets, each 0-255 with no leading zeros. A fixed piece count adds a strong prune: with slots pieces left to place, the remaining digits must number between slots and 3 * slots.

if (parts.size() == 4) { if (start == s.length()) result.add(String.join(".", parts)); return; }
int remaining = s.length() - start, slots = 4 - parts.size();
if (remaining < slots || remaining > 3 * slots) return;          // can't possibly fit
for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
    String piece = s.substring(start, start + len);
    if (len > 1 && piece.charAt(0) == '0') break;                 // "0" is fine, "01" is not
    if (Integer.parseInt(piece) > 255) break;
    parts.add(piece);
    build(s, start + len, parts, result);
    parts.remove(parts.size() - 1);
}

def build(s: str, start: int, parts: list[str], result: list[str]) -> None:
    if len(parts) == 4:
        if start == len(s):
            result.append(".".join(parts))
        return
    remaining, slots = len(s) - start, 4 - len(parts)
    if remaining < slots or remaining > 3 * slots:
        return                                   # can't possibly fit
    for length in range(1, 4):
        if start + length > len(s):
            break                                # a slice past the end is just shorter - no error to stop you
        piece = s[start:start + length]
        if length > 1 and piece[0] == "0":
            break                                # "0" is fine, "01" is not
        if int(piece) > 255:
            break
        parts.append(piece)
        build(s, start + length, parts, result)
        parts.pop()

Each piece's rules are checked the moment it's cut. Dropping the leading-zero rule doesn't just add a few answers: on "010010" it produces 10 addresses (such as 01.0.0.10) where only 2 are valid.

Where you'll see it

Tokenizers and input-method editors segment run-together text into dictionary words; parsers for loosely formatted identifiers (IP addresses, dates, product codes) try each split and validate the pieces. When only one best segmentation is needed, production systems switch to dynamic programming - the same "where's the next cut" recursion, memoized.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. How many ways can "aaaaaa" be partitioned so that every piece is a palindrome?

2. Why prune with "remaining digits must be between slots and 3 * slots" in Restore IP Addresses?

3. "Can this string be segmented into dictionary words?" - backtracking or DP?

Key takeaways

• Partitioning is choose-explore-un-choose over "where does the next piece end".
• Validate each piece as it's cut, and record a copy when the string is used up.
• Precompute expensive piece checks (a palindrome table) instead of repeating them.
• Fixed piece counts allow length-based pruning (IP addresses: slots to 3 * slots digits left).
• Up to 2^(n - 1) partitions exist; existence and minimum questions are DP, not enumeration.