How do you approach Restore IP Addresses?

Place exactly 4 segments, each 1-3 digits.

What are common mistakes on Restore IP Addresses?

Pushing the working array into the results without copying it, so every entry aliases the same array. Forgetting to undo the choice after the recursive call returns. Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.

← Back to problems

Restore IP Addresses

MediumAlgorithms

Description

Given a string `s` of digits, return all possible valid IP addresses that can be formed by inserting dots into `s`. You may not reorder or remove digits. A valid IP address has four parts, each between `0` and `255`, with no leading zeros (except the single digit `0`).

Example 1

Input: s = "25525511135"

Output: ["255.255.11.135","255.255.111.35"]

Explanation: Two valid groupings.

Constraints

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

Restore IP Addresses: approach, complexity and pitfalls

A medium backtracking problem, graded against 4 test cases (2 of them hidden).

The pattern: Backtracking

Systematic exploration of all candidates, abandoning partial ones that cannot work.

Reach for it when you see: "All permutations/combinations/subsets", or constraint puzzles like N-Queens and Sudoku.

More Backtrackingproblems →

If you are stuck

Show the 2-step hint ladder

Place exactly 4 segments, each 1-3 digits.
Reject a segment with a leading zero (unless it is exactly '0') or a value above 255.

The optimal approach

Show the approach: The approach

Backtracking over segment lengths. Try segment lengths 1-3 for each of the four parts, validating range and leading zeros. When four parts consume the whole string, join with dots and record it.

Time: O(1) (at most 3⁴ splits). Space: O(1).

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

Common Backtracking mistakes

These apply to the pattern as a whole, not just this problem.

Pushing the working array into the results without copying it, so every entry aliases the same array.
Forgetting to undo the choice after the recursive call returns.
Deduplicating at the end instead of pruning at the branch - the difference between passing and timing out.