Community Problem

Restore IP Addresses

Difficulty: Medium

Given a string of digits, return every valid IPv4 address that can be formed by inserting three dots, using bounded-depth backtracking.

Restore IP Addresses

Given a string of digits, return every valid IPv4 address that can be formed by inserting three dots, using bounded-depth backtracking.

MEDIUM

Free

backtracking

strings

recursion

By CodeSnatch

May 12, 2026

Updated May 18, 2026

278 views

4.5 (10)

I got this on a Cloudflare phone screen and the interviewer's hint after I started writing nested for-loops was "the search depth is fixed at four. Stop thinking iteration, start thinking recursion." That reframing makes the problem trivial: at every step you decide which 1-to-3 digit prefix is the next octet, and you stop after exactly four octets when the input is consumed. The catalog covered combination-sum and palindrome-partitioning, but it skipped this fixed-arity backtracking variant.

Restore IP Addresses

A valid IPv4 address consists of exactly four integers (each between 0 and 255) separated by single dots. Each integer is written without leading zeros (so 0 is allowed but 00, 01, and 010 are not).

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. You cannot reorder or remove any digits. The order of the returned list does not matter.

Examples

Example 1:

Input: s = "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]
Explanation: Both splittings yield four octets in [0, 255] with no leading-zero violations.

Example 2:

Input: s = "0000"
Output: ["0.0.0.0"]
Explanation: The only valid split is single-zero octets. 00.0.0 is rejected because 00 has a leading zero.

Example 3:

Input: s = "101023"
Output: ["1.0.10.23", "1.0.102.3", "10.1.0.23", "10.10.2.3", "101.0.2.3"]
Explanation: Five distinct splittings produce four valid octets.

Example 4:

Input: s = "1111"
Output: ["1.1.1.1"]
Explanation: A length-4 input has only one valid four-segment split.

Constraints

1 <= s.length <= 20.
s consists only of decimal digits 0-9.

Follow-up

Why is this problem O(1) in the worst case despite looking exponential? Each octet has at most 3 candidate lengths and there are 4 octets, so the search tree has at most 3^4 = 81 leaves. The total work is bounded by a constant, regardless of s.length. The string-length cap (20) is a sanity bound, not a complexity driver.

Solution

JavaScript

Python

Hints

0/4

Hint 1

Hint 2

Hint 3

Hint 4

Solution Walkthrough

Approach: Bounded-Depth Backtracking (O(1) time, O(1) space)

A valid IPv4 address has exactly four octets, so the search tree has depth 4. At each level, we choose how many digits (1, 2, or 3) the next octet consumes, validate the resulting segment, and recurse. When path.length == 4 we accept the candidate only if every input character has been consumed.

Key Insight

The per-step branching factor is at most 3 (octet length 1, 2, or 3), and the depth is fixed at 4. The total number of nodes in the search tree is bounded by 3^4 = 81, regardless of the input length. The string-length cap (20) only matters for early pruning of obviously-impossible inputs.

Algorithm

If s.length < 4 or s.length > 12, return [] (cannot form 4 octets).
Recurse with (start, path). At each level:
- If path.length == 4: emit path.join('.') if start == s.length, else skip.
- Compute remainingChars = s.length - start and remainingOctets = 4 - path.length. If remainingChars < remainingOctets (not enough digits) or remainingChars > 3 * remainingOctets (too many digits), prune.
- For length in 1, 2, 3: extract seg = s[start..start+length]. If seg is a valid octet, push and recurse with start + length.
An octet is valid iff: length in [1, 3], no leading zero unless seg == "0", integer value in [0, 255].

Why It Works

The recursion enumerates every way to partition s into exactly 4 contiguous substrings, with the validity check rejecting illegal partitions. Because every recursion either consumes between 1 and 3 characters or aborts on a validation failure, the search is exhaustive AND finite. The early-prune step (remaining-char count check) is a constant-factor speedup; correctness does not depend on it.

Complexity

Search space

Text

Depth=4, branching <= 3, leaves <= 81
Time    O(1) (bounded constant)
Space   O(1) for recursion stack of depth 4

Pitfalls

Forgetting the leading-zero rule. "01", "00", "010" are all invalid. Only the single "0" octet is allowed.
Not checking start == s.length at depth 4. Without that check, you accept partitions that leave digits unused, e.g. "1.1.1.1" from "11111".
Iterating segment length past s.length - start. Use a bounds guard inside the loop, otherwise substring may produce a short final octet you accidentally accept.

Solution Code

All Problems