We use analytics and advertising cookies to understand how the site is used and whether our ads on Facebook and Instagram work. They are set only if you accept. See our Privacy Policy for details.
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).
A medium backtracking problem, graded against 8 test cases (6 of them hidden).
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 Backtracking problems →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.
These apply to the pattern as a whole, not just this problem.