Restore IP Addresses (LeetCode 93)
A valid IPv4 address is four integers, each between 0 and 255, separated by three single dots, where none of the four integers may carry a leading zero (except the single digit "0" itself).
So "0.1.2.201" and "192.168.1.1" qualify, while something like "0.011.255.245" (a leading zero) or "192.168.1.312" (out of range) does not.
Given a digit-only string s, insert three dots somewhere into it -- without reordering or dropping any digit -- to produce every distinct string that forms a valid IPv4 address this way, returned in any order.
Worked Examples
s = "25525511135"["255.255.11.135","255.255.111.35"]s = "0000"["0.0.0.0"]s = "101023"["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]⚖️Formal Constraints & Bounds
1 <= s.length <= 20sconsists of digits only.
Core Insight
Because every octet is 1-3 digits, the branching factor at each recursive step is bounded by 3 -- so trying all length-1, length-2, and length-3 prefixes at each position and validating them (no leading zero, value in [0, 255]) enumerates the full solution space in a tightly bounded backtracking tree.
Real-World Scenario & Production Applications
Network configuration validators that reconstruct candidate IPv4 addresses from raw log digit streams, and firewall rule auditing tools that must enumerate every syntactically legal address a malformed digit blob could represent.
Subproblems & Recurrence Decomposition3 Phases
At each recursion step, try consuming 1, 2, or 3 digits from the current position as the next IP octet.
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start + length]Step-by-Step Execution Trace Table
| Step | Start Index | Collected Octets parts | Candidate Segment s[start:start+len] | Validity Check (0 ≤ val ≤ 255, no leading 0) | Action | Result / Reason |
|---|---|---|---|---|---|---|
| 1 | 0 | [] | "1" (len 1) | Valid (1) | Recurse | parts = ["1"], start = 1 |
| 2 | 1 | ["1"] | "0" (len 1) | Valid (0) | Recurse | parts = ["1", "0"], start = 2 |
| 3 | 2 | ["1", "0"] | "1" (len 1) | Valid (1) | Recurse | parts = ["1", "0", "1"], start = 3 |
| 4 | 3 | ["1", "0", "1"] | "02" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "02" |
| 5 | 2 | ["1", "0"] | "10" (len 2) | Valid (10) | Recurse | parts = ["1", "0", "10"], start = 4 |
| 6 | 4 | ["1", "0", "10"] | "23" (len 2) | Valid (23), start+len == 6 | ✅ Match | Emits "1.0.10.23" |
| 7 | 1 | ["1"] | "01" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "01" |
s = "25525511135"["255.255.11.135","255.255.111.35"]| Step | Start Index | Collected Octets parts | Candidate Segment s[start:start+len] | Validity Check (0 ≤ val ≤ 255, no leading 0) | Action | Result / Reason |
|---|---|---|---|---|---|---|
| 1 | 0 | [] | "1" (len 1) | Valid (1) | Recurse | parts = ["1"], start = 1 |
| 2 | 1 | ["1"] | "0" (len 1) | Valid (0) | Recurse | parts = ["1", "0"], start = 2 |
| 3 | 2 | ["1", "0"] | "1" (len 1) | Valid (1) | Recurse | parts = ["1", "0", "1"], start = 3 |
| 4 | 3 | ["1", "0", "1"] | "02" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "02" |
| 5 | 2 | ["1", "0"] | "10" (len 2) | Valid (10) | Recurse | parts = ["1", "0", "10"], start = 4 |
| 6 | 4 | ["1", "0", "10"] | "23" (len 2) | Valid (23), start+len == 6 | ✅ Match | Emits "1.0.10.23" |
| 7 | 1 | ["1"] | "01" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "01" |
| 1 | def backtrack(start, parts): |
| 2 | if len(parts) == 4: |
| 3 | if start == n: |
| 4 | res.append('.'.join(parts)) |
| 5 | return |
| 6 | for length in range(1, 4): |
| 7 | if start + length > n: |
| 8 | break |
| 9 | segment = s[start:start + length] |
| 10 | if is_valid(segment): |
| 11 | backtrack(start + length, parts + [segment]) |
| 12 | backtrack(0, []) |
Conceptual Narrative
A clear example of bounded-depth backtracking: the search tree never grows with the input, because an IPv4 address always has exactly 4 octets.
🧭 Conceptual Foundation & Pattern Intuition
Unlike most backtracking problems where the search tree can grow arbitrarily with input size, Restore IP Addresses has two hard limits baked into the problem itself: the recursion is always exactly 4 levels deep (4 octets), and at each level there are only 3 possible branch choices (a 1, 2, or 3 digit segment). That means the entire search tree, no matter how long the input digit string is, never exceeds 3^4 = 81 nodes.
🏟️ The Analogy: Cutting a Ribbon into Exactly 4 Labeled Pieces
Imagine a ribbon of digits that must be cut into exactly 4 pieces, where each piece is a plausible "amount" between 0 and 255. At each cut point, you only ever consider 3 candidate cut lengths (1, 2, or 3 characters) -- never more, because a valid octet can never be longer than 3 digits. You keep cutting until you've made exactly 4 pieces; if you run out of ribbon early, or have ribbon left over after 4 pieces, that attempt doesn't count.
🔑 The Key Idea in the Code
The recursion depth is capped at 4 (len(parts) == 4 is the base case), and the branching factor is capped at 3 -- so this is one of the few backtracking problems whose entire worst-case search space is a small, input-independent constant.
Restore IP Addresses: accepting a multi-digit octet with a leading zero.
"01"and"00"are invalid octets — only a single-character"0"is a valid zero. Converting tointfirst (int("00") == 0) hides this bug because the numeric value looks fine; the check must be on the string form before conversion.Restore IP Addresses: forgetting the length bound. Without capping candidate segment length at 3, a 4+ digit "octet" would be considered — always invalid (
> 255) but wastefully explored, and in pathological string-parsing code, occasionally accepted by an incorrect range check.Restore IP Addresses: requiring 4 parts OR full consumption instead of both. A correct result requires both conditions simultaneously: exactly 4 octets chosen, and every digit of
sconsumed. Checking only one of the two accepts either too-short prefixes or leftover trailing digits as valid.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Digit string + insert exactly 3 dots + each of the 4 resulting segments must be a valid 0-255 octet with no leading zeros.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: at any recursive call, parts holds a prefix of valid octets that together consumed exactly the first start characters of s; success occurs only when len(parts) == 4 and start == len(s).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Accepting an octet like '01' or '00' that has a leading zero but is more than one digit long -- the problem explicitly forbids this.
Recording a result when 4 parts exist but digits remain unconsumed (or vice versa) -- both endpoints (exactly 4 parts AND exactly full consumption) must hold simultaneously.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I backtrack over octet length 1, 2, or 3 at each position. I validate that a candidate octet has no illegal leading zero and its integer value is between 0 and 255. I recurse with the remaining suffix and one more collected octet. Once I have exactly 4 octets, I only record the result if the entire string has been consumed. This bounds the search to a small constant branching factor per position."
Complexity & Mathematical Proof
O(1) (bounded search tree, independent of N beyond a small constant)
Look at the recursion tree: the recursion always terminates by depth 4 (exactly 4 octets), and at each level branches into at most 3 candidate octet lengths (1, 2, or 3 digits). This bounds the entire search tree to at most 3^4 = 81 nodes regardless of how long the input string s is (up to its max constraint length of 20).
O(1) Auxiliary (beyond output)
Look at our memory allocations: the call stack never exceeds depth 4 (one frame per octet): O(1). The parts list holds at most 4 strings at any time: O(1). Only the final output list of restored IP strings grows with the number of valid combinations found.
Derivation Progression
The recursion only ever records a result (or discards a branch) once exactly 4 octets have been chosen.
Each octet can only be 1, 2, or 3 digits long, capping branching regardless of |s|.
The entire search space is bounded by a small constant, independent of the input string's length.
Variable Definitions
Branching factor: candidate octet lengths (1, 2, or 3 digits) tried at each of the 4 levels
Fixed recursion depth: exactly 4 octets make a valid IPv4 address
Memory Architecture & Bounds
O(1) At most 4 recursion frames deep
O(1) parts list holds at most 4 octet strings
O(K) Where K is the number of valid restored IPs found (at most a handful)
Boundary Best / Worst Cases
if the string length immediately rules out any valid split.
constant-bounded search.
bounded search of at most 81 nodes, independent of input length.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "restore valid IP addresses", "four integers separated by dots". Bounded-depth octet partitioning: exactly 4 parts, each part in , no leading zeros.
. Pruning bounds search space to at most states (ms).
Leading zeros: "01" is invalid, but "0" is valid! If , the only valid segment is "0". Also prune if remaining length cannot form valid octets: .
Restore IP Addresses (LeetCode 93)
A valid IPv4 address is four integers, each between 0 and 255, separated by three single dots, where none of the four integers may carry a leading zero (except the single digit "0" itself).
So "0.1.2.201" and "192.168.1.1" qualify, while something like "0.011.255.245" (a leading zero) or "192.168.1.312" (out of range) does not.
Given a digit-only string s, insert three dots somewhere into it -- without reordering or dropping any digit -- to produce every distinct string that forms a valid IPv4 address this way, returned in any order.
Worked Examples
s = "25525511135"["255.255.11.135","255.255.111.35"]s = "0000"["0.0.0.0"]s = "101023"["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]⚖️Formal Constraints & Bounds
1 <= s.length <= 20sconsists of digits only.
Core Insight
Because every octet is 1-3 digits, the branching factor at each recursive step is bounded by 3 -- so trying all length-1, length-2, and length-3 prefixes at each position and validating them (no leading zero, value in [0, 255]) enumerates the full solution space in a tightly bounded backtracking tree.
Real-World Scenario & Production Applications
Network configuration validators that reconstruct candidate IPv4 addresses from raw log digit streams, and firewall rule auditing tools that must enumerate every syntactically legal address a malformed digit blob could represent.
Subproblems & Recurrence Decomposition3 Phases
At each recursion step, try consuming 1, 2, or 3 digits from the current position as the next IP octet.
for length in range(1, 4):
if start + length > len(s):
break
segment = s[start:start + length]Step-by-Step Execution Trace Table
| Step | Start Index | Collected Octets parts | Candidate Segment s[start:start+len] | Validity Check (0 ≤ val ≤ 255, no leading 0) | Action | Result / Reason |
|---|---|---|---|---|---|---|
| 1 | 0 | [] | "1" (len 1) | Valid (1) | Recurse | parts = ["1"], start = 1 |
| 2 | 1 | ["1"] | "0" (len 1) | Valid (0) | Recurse | parts = ["1", "0"], start = 2 |
| 3 | 2 | ["1", "0"] | "1" (len 1) | Valid (1) | Recurse | parts = ["1", "0", "1"], start = 3 |
| 4 | 3 | ["1", "0", "1"] | "02" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "02" |
| 5 | 2 | ["1", "0"] | "10" (len 2) | Valid (10) | Recurse | parts = ["1", "0", "10"], start = 4 |
| 6 | 4 | ["1", "0", "10"] | "23" (len 2) | Valid (23), start+len == 6 | ✅ Match | Emits "1.0.10.23" |
| 7 | 1 | ["1"] | "01" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "01" |
s = "25525511135"["255.255.11.135","255.255.111.35"]| Step | Start Index | Collected Octets parts | Candidate Segment s[start:start+len] | Validity Check (0 ≤ val ≤ 255, no leading 0) | Action | Result / Reason |
|---|---|---|---|---|---|---|
| 1 | 0 | [] | "1" (len 1) | Valid (1) | Recurse | parts = ["1"], start = 1 |
| 2 | 1 | ["1"] | "0" (len 1) | Valid (0) | Recurse | parts = ["1", "0"], start = 2 |
| 3 | 2 | ["1", "0"] | "1" (len 1) | Valid (1) | Recurse | parts = ["1", "0", "1"], start = 3 |
| 4 | 3 | ["1", "0", "1"] | "02" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "02" |
| 5 | 2 | ["1", "0"] | "10" (len 2) | Valid (10) | Recurse | parts = ["1", "0", "10"], start = 4 |
| 6 | 4 | ["1", "0", "10"] | "23" (len 2) | Valid (23), start+len == 6 | ✅ Match | Emits "1.0.10.23" |
| 7 | 1 | ["1"] | "01" (len 2) | ❌ Invalid: leading zero | Prune | Cannot use "01" |
| 1 | def backtrack(start, parts): |
| 2 | if len(parts) == 4: |
| 3 | if start == n: |
| 4 | res.append('.'.join(parts)) |
| 5 | return |
| 6 | for length in range(1, 4): |
| 7 | if start + length > n: |
| 8 | break |
| 9 | segment = s[start:start + length] |
| 10 | if is_valid(segment): |
| 11 | backtrack(start + length, parts + [segment]) |
| 12 | backtrack(0, []) |
Conceptual Narrative
A clear example of bounded-depth backtracking: the search tree never grows with the input, because an IPv4 address always has exactly 4 octets.
🧭 Conceptual Foundation & Pattern Intuition
Unlike most backtracking problems where the search tree can grow arbitrarily with input size, Restore IP Addresses has two hard limits baked into the problem itself: the recursion is always exactly 4 levels deep (4 octets), and at each level there are only 3 possible branch choices (a 1, 2, or 3 digit segment). That means the entire search tree, no matter how long the input digit string is, never exceeds 3^4 = 81 nodes.
🏟️ The Analogy: Cutting a Ribbon into Exactly 4 Labeled Pieces
Imagine a ribbon of digits that must be cut into exactly 4 pieces, where each piece is a plausible "amount" between 0 and 255. At each cut point, you only ever consider 3 candidate cut lengths (1, 2, or 3 characters) -- never more, because a valid octet can never be longer than 3 digits. You keep cutting until you've made exactly 4 pieces; if you run out of ribbon early, or have ribbon left over after 4 pieces, that attempt doesn't count.
🔑 The Key Idea in the Code
The recursion depth is capped at 4 (len(parts) == 4 is the base case), and the branching factor is capped at 3 -- so this is one of the few backtracking problems whose entire worst-case search space is a small, input-independent constant.
Restore IP Addresses: accepting a multi-digit octet with a leading zero.
"01"and"00"are invalid octets — only a single-character"0"is a valid zero. Converting tointfirst (int("00") == 0) hides this bug because the numeric value looks fine; the check must be on the string form before conversion.Restore IP Addresses: forgetting the length bound. Without capping candidate segment length at 3, a 4+ digit "octet" would be considered — always invalid (
> 255) but wastefully explored, and in pathological string-parsing code, occasionally accepted by an incorrect range check.Restore IP Addresses: requiring 4 parts OR full consumption instead of both. A correct result requires both conditions simultaneously: exactly 4 octets chosen, and every digit of
sconsumed. Checking only one of the two accepts either too-short prefixes or leftover trailing digits as valid.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Digit string + insert exactly 3 dots + each of the 4 resulting segments must be a valid 0-255 octet with no leading zeros.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: at any recursive call, parts holds a prefix of valid octets that together consumed exactly the first start characters of s; success occurs only when len(parts) == 4 and start == len(s).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Accepting an octet like '01' or '00' that has a leading zero but is more than one digit long -- the problem explicitly forbids this.
Recording a result when 4 parts exist but digits remain unconsumed (or vice versa) -- both endpoints (exactly 4 parts AND exactly full consumption) must hold simultaneously.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I backtrack over octet length 1, 2, or 3 at each position. I validate that a candidate octet has no illegal leading zero and its integer value is between 0 and 255. I recurse with the remaining suffix and one more collected octet. Once I have exactly 4 octets, I only record the result if the entire string has been consumed. This bounds the search to a small constant branching factor per position."
Complexity & Mathematical Proof
O(1) (bounded search tree, independent of N beyond a small constant)
Look at the recursion tree: the recursion always terminates by depth 4 (exactly 4 octets), and at each level branches into at most 3 candidate octet lengths (1, 2, or 3 digits). This bounds the entire search tree to at most 3^4 = 81 nodes regardless of how long the input string s is (up to its max constraint length of 20).
O(1) Auxiliary (beyond output)
Look at our memory allocations: the call stack never exceeds depth 4 (one frame per octet): O(1). The parts list holds at most 4 strings at any time: O(1). Only the final output list of restored IP strings grows with the number of valid combinations found.
Derivation Progression
The recursion only ever records a result (or discards a branch) once exactly 4 octets have been chosen.
Each octet can only be 1, 2, or 3 digits long, capping branching regardless of |s|.
The entire search space is bounded by a small constant, independent of the input string's length.
Variable Definitions
Branching factor: candidate octet lengths (1, 2, or 3 digits) tried at each of the 4 levels
Fixed recursion depth: exactly 4 octets make a valid IPv4 address
Memory Architecture & Bounds
O(1) At most 4 recursion frames deep
O(1) parts list holds at most 4 octet strings
O(K) Where K is the number of valid restored IPs found (at most a handful)
Boundary Best / Worst Cases
if the string length immediately rules out any valid split.
constant-bounded search.
bounded search of at most 81 nodes, independent of input length.
Decision & State-Space Search Tree
Senior SWE Deconstruction & Hardware Caveats
Triggers: "restore valid IP addresses", "four integers separated by dots". Bounded-depth octet partitioning: exactly 4 parts, each part in , no leading zeros.
. Pruning bounds search space to at most states (ms).
Leading zeros: "01" is invalid, but "0" is valid! If , the only valid segment is "0". Also prune if remaining length cannot form valid octets: .