Restore IP Addresses: Backtracking with Constraints

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers separated by dots, where each integer is between 0 and 255 and has no leading zeros (except the number "0" itself).

This is LeetCode 93: Restore IP Addresses, and it is a clean example of constrained string partitioning solved with backtracking. You are not choosing from a set of candidates. You are deciding where to place three dots in a digit string, splitting it into exactly four segments that each satisfy a numeric constraint. The pruning rules are tight, and the bounded input length (at most 12 digits) means the search space is small enough that backtracking runs in constant time.

Why this problem matters

Restore IP Addresses sits at the intersection of two patterns that show up across dozens of problems: constrained string partitioning and validation-based backtracking. You are partitioning a string into a fixed number of parts, and each part must pass a validation check. The same structure appears in Palindrome Partitioning (LeetCode 131), where each part must be a palindrome, and in decoding problems where each segment maps to a valid character.

The problem also teaches you how tight constraints shrink the search space. Each segment can be 1, 2, or 3 digits long. There are exactly 4 segments. The input has at most 12 characters. That means the total number of ways to place three dots is at most 3^3 = 27, and most of those get pruned immediately. Unlike open-ended backtracking problems where the tree can grow exponentially, Restore IP Addresses has a bounded, predictable search space.

Finally, the leading-zero rule is a common interview trap. "0" is valid, but "00", "01", and "012" are not. Getting this check right is the difference between a correct and an incorrect solution.

The approach

Think of the problem as placing three dots to split the string into four segments. At each step in the recursion, you try taking 1, 2, or 3 digits as the current segment. For each choice, you validate the segment:

1. The numeric value must be between 0 and 255 (inclusive).
2. No leading zeros: if the segment has more than one digit, the first digit cannot be "0".
3. After placing all four segments, every digit in the string must be used.

The algorithm works like this:

1. Start with zero parts and the full string as remaining input.
2. Try taking 1, 2, or 3 characters from the front of the remaining string as the next segment.
3. If the segment is valid (0 to 255, no leading zeros), add it to the current parts and recurse on the rest of the string.
4. If you have exactly 4 parts and no characters remain, record the IP address.
5. If you have 4 parts but characters remain, or if the remaining string is too long or too short for the parts still needed, prune.

The backtracking solution

def restoreIpAddresses(s: str) -> list[str]:
    result = []

    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append(".".join(parts))
            return

        for length in range(1, 4):
            if start + length > len(s):
                break

            segment = s[start:start + length]

            if len(segment) > 1 and segment[0] == "0":
                break

            if int(segment) > 255:
                break

            backtrack(start + length, parts + [segment])

    backtrack(0, [])
    return result

Let's break this down.

The outer function initializes an empty result list and calls backtrack with start index 0 and an empty parts list.

Inside backtrack, the base case checks whether you have exactly 4 parts. If you do and the start index has reached the end of the string, every digit is accounted for and you have a valid IP. Join the parts with dots and record it. If you have 4 parts but digits remain, return without recording (this combination does not use all digits).

The for loop tries segment lengths of 1, 2, and 3. For each length, three checks happen in sequence:

• Bounds check: if start + length exceeds the string length, there are not enough digits left. Break.
• Leading zero check: if the segment has more than one digit and starts with "0", it has a leading zero. Break (not continue), because a longer segment starting with "0" would also have a leading zero.
• Range check: if the integer value exceeds 255, break. A longer segment would be even larger.

Notice that all three checks use break rather than continue. This is because the checks are monotonic: if a 2-digit segment fails, a 3-digit segment will also fail for the same reason (leading zero or too large). Breaking skips the longer options and prunes the branch.

The recursive call passes parts + [segment], which creates a new list. There is no explicit unchoose step because list concatenation is non-mutating. The backtracking is implicit, just like in Generate Parentheses.

Visual walkthrough

Let's trace through the algorithm with s = "25525511135". Watch how the three pruning checks (bounds, leading zeros, range) eliminate invalid branches, and how the algorithm finds exactly two valid IP addresses.

The key observation is that most branches die early. The segment "552" is pruned immediately because it exceeds 255. The segment "1135" is pruned for the same reason. The leading-zero check would prune segments like "01" or "025" if they appeared. With three pruning rules and a maximum of 4 levels of recursion, the tree stays small.

Complexity analysis

Time: At each of the 4 levels, you try at most 3 segment lengths. That gives at most 3^4 = 81 paths through the recursion tree. The input is capped at 12 characters (any longer and you cannot form a valid IP), so the work per path is bounded. The total time is O(1) with respect to input length, because the problem constraints cap everything at constant values. In practice, pruning reduces the actual work well below 81 paths.

Space: The recursion stack is at most 4 levels deep. Each level stores a parts list with at most 4 segments of at most 3 characters each. The output list has at most a constant number of valid IPs (bounded by the 81 paths). Everything is O(1).

Edge cases

Before submitting, check these:

• All zeros: s = "0000" should return ["0.0.0.0"]. Each segment is "0", which is valid. But s = "00000" returns [] because 5 digits cannot form a valid 4-part IP where one segment is "00" (leading zero).
• Minimum length: The shortest valid input is 4 digits (e.g., "1111" produces ["1.1.1.1"]). Any input shorter than 4 characters returns [].
• Maximum length: The longest valid input is 12 digits (e.g., "255255255255" produces ["255.255.255.255"]). Any input longer than 12 characters returns [].
• Leading zeros in segments: "010010" includes valid results like "0.10.0.10" and "0.100.1.0", but not "01.0.01.0" or "0.1.001.0" because multi-digit segments cannot start with "0".
• Single valid result: "0000" has exactly one valid IP. "255255255255" also has exactly one.

The building blocks

This problem is built on two core reusable patterns that CodeBricks drills independently.

Constrained string partitioning

The template for partitioning a string into segments with validation:

def partition(s, start, parts, result):
    if len(parts) == target_count:
        if start == len(s):
            result.append(format(parts))
        return

    for length in range(1, max_length + 1):
        if start + length > len(s):
            break

        segment = s[start:start + length]

        if not is_valid(segment):
            break

        partition(s, start + length, parts + [segment], result)

This template handles any problem where you split a string into a fixed number of validated parts. In Restore IP Addresses, target_count is 4, max_length is 3, and is_valid checks the 0-255 range and leading zeros. In Palindrome Partitioning (LeetCode 131), there is no fixed count, max_length is unbounded, and is_valid checks for palindromes.

Validation backtracking

The pattern of trying multiple choices and pruning based on a validation function:

for choice in possible_choices:
    if not valid(choice):
        break  # or continue, depending on monotonicity

    apply(choice)
    recurse()
    undo(choice)

The key insight is knowing when to break vs continue. If your validation is monotonic (longer segments only get worse), use break to prune all remaining choices at once. If each choice is independent, use continue. In Restore IP Addresses, the checks are monotonic: a longer segment that starts with "0" still starts with "0", and a longer segment with value above 255 will have an even larger value.

This same pattern applies to Combination Sum (break when candidate exceeds remaining, because sorted candidates only get bigger) and Generate Parentheses (prune when counter constraints are violated).

Common mistakes

1. Using continue instead of break. If a 2-digit segment has a leading zero or exceeds 255, a 3-digit segment will too. Using continue wastes time checking a longer segment that is guaranteed to fail. Using break correctly prunes the inner loop.

2. Forgetting the leading-zero check. Without it, you would accept segments like "01" and "001", producing invalid IP addresses. The check must be len(segment) > 1 and segment[0] == "0", applied before the numeric range check.

3. Not verifying all digits are used. If you only check len(parts) == 4 without checking start == len(s), you would record partial IPs that leave trailing digits unused. Both conditions are required for a valid result.

4. Off-by-one in the range check. The valid range is 0 to 255, inclusive. Checking int(segment) > 255 is correct. Checking int(segment) >= 255 would incorrectly exclude the segment "255".

From understanding to recall

You see the recursion tree. You understand how trying 1, 2, or 3 digits at each level with validation-based pruning produces only valid IP addresses. But can you write this solution from scratch in under two minutes without looking anything up?

That is what interviews demand. The combination of string slicing, numeric validation, and the leading-zero edge case creates enough surface area for mistakes. Under pressure, people forget the break-vs-continue distinction, botch the leading-zero check, or omit the "all digits used" guard. These are not conceptual gaps. They are recall problems.

Spaced repetition fixes recall. You practice writing the constrained partitioning template and the IP-specific validation from memory at increasing intervals. After a few rounds, the pattern is automatic. You see "restore IP addresses LeetCode" and the code flows out without hesitation.

The constrained string partitioning pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping the patterns stick.

Related posts

• Combination Sum - Another backtracking problem with pruning. Compare the pruning strategies: Combination Sum breaks when a sorted candidate exceeds the remaining target, while Restore IP Addresses breaks when a segment exceeds 255 or has a leading zero. Same template, different constraints.
• Generate Parentheses - Constrained backtracking with two simple rules. Generate Parentheses prunes on counter constraints (open/close counts), while Restore IP Addresses prunes on segment validation (range and format). Both show how tight constraints keep the search space small.

CodeBricks breaks Restore IP Addresses into its constrained partitioning building block, then drills it independently with spaced repetition. You type the validation loop and the recursive skeleton from scratch until it is automatic. When a partitioning problem shows up in your interview, you do not think about it. You just write it.