Restore IP Addresses

Explanation & Solution

Description

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. Each integer is between 0 and 255 (inclusive) and cannot have leading zeros (except for the number 0 itself).

Input: s = "25525511135"

Output:["255.255.11.135","255.255.111.35"]

255.255.11.135

255.255.111.35

Explanation: The two valid IP addresses are formed by placing dots at different positions.

Constraints

1 <= s.length <= 20
s consists of digits only.

Approach

Subsets pattern

1. Set Up Backtracking

Initialize an empty result array.
Start recursive exploration from index 0 with an empty parts array.
Each part represents one segment of the IP address.

2. Base Case — Four Segments Formed

When parts.length === 4, check if all characters have been consumed (start === s.length).
If yes, join the 4 parts with dots and add to the result.
If characters remain, this path is invalid — backtrack.

3. Try Segments of Length 1, 2, and 3

From the current position, try taking 1, 2, or 3 characters as the next IP segment.
Bounds check: Ensure we don't go past the end of the string.
Leading zeros: If the segment has more than 1 character and starts with '0', it is invalid. We break since longer segments would also have a leading zero.
Range check: If parseInt(part) > 255, the segment exceeds the valid range. We break since adding more digits would only increase the value.

4. Recurse and Backtrack

Push the valid segment, recurse from start + len, then pop to backtrack.
This explores all valid ways to partition the string into 4 octets.

5. Sort and Return

After all combinations are explored, sort the result for consistent output.
Return the list of all valid IP addresses.

Key Insight

The key technique is constrained backtracking: by limiting each segment to 1-3 digits and pruning with leading-zero and range checks, the search space stays very small.

Time

O(3^4) = O(1) since the search space is bounded — there are at most 81 ways to place 3 dots.

Space

O(1) extra space (not counting output), with recursion depth always exactly 4.

Visualization

Input:

[2, 5, 5, 2, 5, 5, 1, 1, 1, 3, 5]

—

No animation available

Left (L)Right (R)ConvergedDone

0 steps

Solution Code

Increasing Subsequences