Restore IP Addresses

The trap is to think “place three dots.” The useful model is narrower: choose exactly four contiguous digit segments, validate each one immediately, and prune any path that cannot consume the remaining digits.

The Restore IP Addresses solution is a bounded backtracking search. Every recursive level chooses one segment of length 1, 2, or 3, because valid values cannot need more than three digits.

The contract and the search shape

A valid result must satisfy all of these conditions:

• It uses every digit in the input, in the original order.
• It contains exactly four segments.
• Each segment represents a value from 0 through 255.
• A segment with multiple digits cannot start with 0.
• The output order does not matter.

So this is a bounded string-partition problem. We are splitting the digit string into four parts, not generating permutations and not choosing arbitrary subsets.

At each recursive step:

1. Choose a contiguous segment.
2. Reject it if its encoding is invalid.
3. Add it to the current path.
4. Recurse on the remaining suffix.
5. Remove it before trying the next segment.

That last step is the backtracking operation. The path is shared mutable state; each branch must leave it exactly as it found it.

A blind approach could try every placement of three dots and validate only complete candidates. That works as a baseline, but it hides the useful structure. The four-segment contract gives us a small search tree, and local validation lets us kill bad branches before they grow.

Reject the wrong branches early

There are two kinds of pruning here: local validity and remaining capacity.

Local validity

A candidate segment is invalid when:

• It has a leading zero and more than one digit.
• Its numeric value exceeds 255.

For example:

• "0" is valid.
• "00" is invalid because of the leading zero.
• "25" is valid.
• "256" is invalid because its value is too large.

Trying at most three digits is already a structural bound. A four-digit segment cannot represent a value from 0 through 255 under this problem's rules.

Remaining-length pruning

Suppose the current path has chosen some segments, and r segments remain. Let remaining_digits be the number of unconsumed characters.

Each remaining segment must contain at least one digit and at most three digits. Therefore:

[ r \leq \text{remaining_digits} \leq 3r ]

If the suffix is too short, there are not enough digits to form the remaining segments. If it is too long, the remaining segments cannot consume it.

This check catches failures before recursion:

• An input shorter than four digits cannot produce four non-empty segments.
• An input longer than twelve digits cannot fit four segments of at most three digits.
• A partial path can also become impossible even when the original input length looked feasible.

The outer length check is a quick version of the same argument:

if len(s) < 4 or len(s) > 12:
    return []

The recursive version is still valuable because it reasons about the suffix after earlier choices.

Define the state and transition

The recursive state needs only three pieces of information:

• index: where the next segment begins in s
• path: the segments chosen so far
• len(path): how many of the four required segments have been chosen

At a state, try endpoints that produce segment lengths 1, 2, and 3, stopping at the end of the string.

For example, if index == 2, the candidates are:

s[2:3], s[2:4], s[2:5]

Each candidate is contiguous. Digits are never skipped, reordered, or reused.

The core transition is:

append candidate
recurse from the candidate's end
pop candidate

The invariant we want is simple:

The segments in path concatenate to exactly the prefix s[:index], and every segment in path is locally valid.

Appending preserves that invariant by consuming a valid next segment. Popping restores the previous state so the next sibling branch starts from the same prefix.

Base case and correctness proof

A path is an answer only when both obligations are complete:

len(path) == 4
index == len(s)

Both checks matter.

• Four segments with digits remaining is invalid.
• All digits consumed with fewer than four segments is invalid.
• Four segments and all digits consumed is valid, assuming every segment passed local validation.

The remaining-length check often rejects those first two cases before they reach the base case, but the base case should still express the exact acceptance condition.

Completeness

Take any valid address formed from s. Its four segments have lengths between 1 and 3.

At the first recursive level, the search tries every legal first length. It therefore includes the valid address's first segment length. At the second level, it tries every legal second length, including the address's second segment length. The same reasoning applies to the third and fourth segments.

Eventually, the search follows the exact sequence of boundaries used by the valid address and reaches the accepting base case.

Therefore, every valid address is explored.

Soundness

Every accepted path:

• contains exactly four segments,
• consumes the entire input,
• uses each digit exactly once and in order,
• contains no multi-digit leading zero,
• contains no value above 255.

So every emitted string is valid.

Uniqueness

A placement of the three dots is completely determined by the four segment boundaries. The recursion chooses those boundaries in order, and each sequence of segment lengths is explored once.

Therefore, the same address is not generated through two different paths.

Dry-run: valid and dead branches

Use s = "101023".

One successful path is:

1 | 0 | 10 | 23

The first few decisions look like this:

The failed "02" branch is stopped before recursion. That is the point of validating locally.

The search then continues to find other valid partitions, including:

1.0.102.3
10.1.0.23
10.10.2.3
101.0.2.3

Two other failure patterns are worth tracing.

Leading-zero failure

At a position containing "0", the one-digit candidate "0" may be valid. The next candidate, "01", is not.

Once the first digit is zero, every longer candidate from that position is invalid. The implementation can stop trying longer candidates immediately.

Range failure

Suppose the remaining suffix begins with "256":

• "2" is valid.
• "25" is valid.
• "256" is rejected because it exceeds 255.

The branch does not continue with "256" as a segment. A candidate that fails its local range constraint cannot become valid by recursing.

The matching pop() is just as important as the rejection checks. After exploring ["1", "0", "10", "23"], the algorithm removes "23" before trying another fourth segment. Without that restoration, the next branch would inherit stale state and produce malformed paths.

Write the Python solution from the invariant

Here is an interview-readable Python implementation:

from typing import List


def restoreIpAddresses(s: str) -> List[str]:
    n = len(s)
    result: List[str] = []
    path: List[str] = []

    # Four non-empty segments, each at most three digits.
    if n < 4 or n > 12:
        return result

    def backtrack(index: int) -> None:
        chosen = len(path)
        remaining_segments = 4 - chosen
        remaining_digits = n - index

        # Every remaining segment needs 1..3 digits.
        if (
            remaining_digits < remaining_segments
            or remaining_digits > 3 * remaining_segments
        ):
            return

        # All four segments have been chosen.
        if remaining_segments == 0:
            if index == n:
                result.append(".".join(path))
            return

        # Try a segment of length 1, 2, or 3.
        for end in range(index, min(index + 3, n)):
            segment = s[index : end + 1]

            # A multi-digit segment cannot begin with zero.
            if len(segment) > 1 and segment[0] == "0":
                break

            # The input contains digits only, so int conversion is safe.
            if int(segment) > 255:
                continue

            path.append(segment)
            backtrack(end + 1)
            path.pop()

    backtrack(0)
    return result

Each variable has a direct obligation:

• index tracks which digits have already been consumed.
• path stores the current sequence of segments.
• remaining_segments enforces the exact four-part contract.
• remaining_digits supports capacity pruning.
• result stores every complete valid address.

The implementation builds segments as strings and uses ".".join(path) only at an accepting leaf. That avoids managing a trailing dot during recursion.

The break for a leading zero deserves attention. If the candidate is "0", it may be valid. Any longer candidate starting at the same position begins with zero and is invalid, so no later endpoint at that position can recover.

The pop() must match every successful append(). This is the classic mutable-state failure mode:

path.append(segment)
backtrack(end + 1)
# If path.pop() is missing, sibling branches see the old segment.

That bug can leave extra segments in later results or make valid paths appear impossible. Read the error. Trace the state. Fix the assumption.

Do not delegate this problem to a networking parser. The coding problem defines its own exact acceptance rules, and a general-purpose parser may accept formats or behaviors that do not match the contract. Implement the stated rules directly.

Complexity and interview reliability checks

At most four segment slots are filled, and each slot tries at most three lengths. The search therefore explores at most:

[ 3^4 ]

segment-length paths before pruning. For a generalized input length n, validating and slicing candidates adds a small factor related to segment length, so a common bound is:

[ O(3^4 \cdot n) ]

The important practical point is that the depth and branching factor are fixed by the address format. This is a small, bounded search, not an unstructured exponential search over arbitrary subsets.

Auxiliary space is:

[ O(4) ]

for the recursion path and call stack, excluding returned output. In Python, the emitted strings and the result list require additional output space. That storage is unavoidable when the task asks for every valid address.

Test the boundaries deliberately:

During an interview, verify four things before you move on:

1. Every accepted result consumes all digits.
2. Every accepted result contains exactly four segments.
3. Leading-zero and range failures stop before deeper recursion.
4. Every append() has a matching pop().

The transferable rule is compact:

When a problem asks for every contiguous partition into a fixed number of locally constrained pieces, search the boundaries. Choose, validate, recurse, undo. Prune using the minimum and maximum capacity of the remaining pieces.

That is the real Restore IP Addresses pattern: a small search tree made reliable by explicit obligations.