Restore IP Addresses: 4-Segment Backtracking Pattern

Problem Statement#

You are given a string s containing only digits. Return all possible valid IP addresses that can be formed by inserting three dots. A valid IPv4 address has exactly four integer segments separated by dots, where each integer is between 0 and 255 inclusive and cannot have leading zeros (so 01 is invalid, but 0 alone is fine).

For s = "25525511135", the answer is ["255.255.11.135", "255.255.111.35"]. The string length is bounded by 12 (four segments of at most three digits each), which makes pruning very effective.

Why This Problem Matters#

LeetCode 93 is a recurring medium-tier interview at Meta, Amazon, Microsoft, and Bloomberg. It looks deceptively simple but rewards candidates who can express bounded backtracking cleanly: exactly four parts, exactly the whole string consumed, exactly the value range and leading-zero rules. Interviewers use it to filter out candidates who write generic "try every split" loops without any pruning.

The problem also sits in the same family as Word Break II, Palindrome Partitioning, and Expression Add Operators — once you recognize the partition-with-validation shape, you can solve all of them with the same template.

The Core Insight (decision tree / state space)#

State: the current start index and the list of segments collected so far (parts). At each node we choose a length of 1, 2, or 3 for the next segment. We stop and record a leaf whenever len(parts) == 4 AND start == n simultaneously. Any other terminal state is pruned.

Three constraints prune the decision tree aggressively:

1. The segment is empty or longer than three digits — invalid.
2. The segment starts with 0 and has more than one digit — invalid (no leading zeros).
3. The integer value exceeds 255 — invalid.

Because the string has length at most 12 and we make exactly three cuts among at most three positions each, the total number of expansions is bounded by 3^3 = 27 leaves in the worst case before validation. That is why this problem is technically O(1) in practice.

Visual Dry Run (recursion tree)#

For s = "101023":

                bt(start=0, parts=[])
            /           |             \
         "1"           "10"          "101"
       bt(1,[1])    bt(2,[10])     bt(3,[101])
       /  |  \       / | \           ...
     "0" "01" "010"
     ^    ^     ^
   valid invalid (leading zero) -> pruned
   bt(2,[1,0])  ...
     /  |  \
   "1" "10" "102"
       ...
   reach 4 parts and start==n -> "1.0.10.23"
   ...
   another leaf -> "1.0.102.3"
   ...
   "10.10.2.3", "10.1.0.23", etc.

The tree is shallow — only 4 levels deep — and most branches die early due to leading-zero or "value > 255" pruning.

Solution (Optimal) — Python + JavaScript with backtracking template, complexity#

def restoreIpAddresses(s):
    n, result = len(s), []
    if n < 4 or n > 12:
        return result
 
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == n:
                result.append('.'.join(parts))
            return
        for length in range(1, 4):
            if start + length > n:
                break
            seg = s[start:start + length]
            if (len(seg) > 1 and seg[0] == '0') or int(seg) > 255:
                continue
            parts.append(seg)
            backtrack(start + length, parts)
            parts.pop()
 
    backtrack(0, [])
    return result

function restoreIpAddresses(s) {
  const n = s.length;
  const result = [];
  if (n < 4 || n > 12) return result;
 
  const backtrack = (start, parts) => {
    if (parts.length === 4) {
      if (start === n) result.push(parts.join('.'));
      return;
    }
    for (let length = 1; length <= 3; length++) {
      if (start + length > n) break;
      const seg = s.slice(start, start + length);
      if ((seg.length > 1 && seg[0] === '0') || Number(seg) > 255) continue;
      parts.push(seg);
      backtrack(start + length, parts);
      parts.pop();
    }
  };
 
  backtrack(0, []);
  return result;
}

Complexity: time is O(1) because the input length is bounded by 12 and each recursion level branches at most 3 ways, giving at most 3^4 = 81 nodes. Space is O(1) for the same reason, ignoring the output list.

Common Mistakes#

• Using break instead of continue for the leading-zero check. A break would skip lengths 2 and 3 even though they are categorically invalid — but a longer segment with the same prefix would still be invalid, so continue is the safer (and correct) choice when seg[0] == '0'. Either way, after seg[0] == '0' you should NOT recurse, but you also should not skip evaluating shorter valid prefixes. In practice break after a leading-zero match works because once you take "0", any longer slice also starts with "0" and is invalid; continue is equivalent here.
• Forgetting to require start == n at the leaf. A 4-segment partition that does not consume the whole string is invalid.
• Not bounding by n in [4, 12] upfront — saves time on adversarial inputs.
• Off-by-one in the slice bounds: use s[start:start+length].

Interview Tips#

• Mention the bounded length up front: "The answer space is at most 3^3 leaves, so this is O(1) in practice."
• Emphasize the two leaf conditions — len(parts) == 4 AND start == n — interviewers love hearing about both.
• Walk through "0000" to demonstrate leading-zero handling. The only valid output is 0.0.0.0.
• Compare to Word Break II (LeetCode 140) and Palindrome Partitioning (LeetCode 131) to show pattern recognition.

Follow-up Questions#

• Restore IPv6 addresses — eight 16-bit hex segments. Same template, different validation.
• Word Break II (LeetCode 140): partition into dictionary words.
• Different Ways to Add Parentheses (LeetCode 241): divide-and-conquer cousin.
• Count valid IPs without enumerating — pure DP, still O(n).

Key Takeaways#

• Restore IP Addresses is a bounded-backtracking classic — exactly four parts, exactly the whole string consumed.
• The decision tree has at most 3^4 = 81 leaves; pruning kills most branches early.
• Leading zeros are the most common bug; always check len(seg) > 1 and seg[0] == '0'.
• Time and space are O(1) because the input size is fixed at 12.
• The template generalizes to Word Break II, Palindrome Partitioning, and Expression Add Operators.
• A FAANG-favorite that filters candidates who can express constraint validation cleanly inside recursion.

Sources:

• 93. Restore IP Addresses - In-Depth Explanation
• 93. Restore IP Addresses - Detailed Explanation