Generate all valid IP addresses from a string
Problem
Given a string of digits, return every valid IPv4 address you can form by inserting three dots. Each of the four parts must be between 0 and 255 and must not have a leading zero (so "0" is allowed but "01" is not).
Example 1
Input: "25525511135" Output: ["255.255.11.135", "255.255.111.35"]
Also asked as: Program to generate all possible valid IP addresses from given string
Test cases
Case 1
Input: "25525511135" Expected (any order): ["255.255.11.135","255.255.111.35"]
Case 2
Input: "101023" Expected (any order): ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
Case 3
Input: "0000" Expected (any order): ["0.0.0.0"]
Case 4
Input: "123" Expected (any order): []
View solutionHide solution1 approach
1. Backtracking with 4 segments
Time O(1) — at most 3⁴ splitsSpace O(1)
Place 3 dots. Each of the 4 parts is 1–3 digits, ≤ 255, and has no leading zero (unless it is "0").
function restoreIps(s) { const res = []; const valid = (seg) => seg.length >= 1 && seg.length <= 3 && (seg === '0' || (seg[0] !== '0' && +seg <= 255)); const bt = (start, parts) => { if (parts.length === 4) { if (start === s.length) res.push(parts.join('.')); return; } for (let len = 1; len <= 3 && start + len <= s.length; len++) { const seg = s.slice(start, start + len); if (valid(seg)) bt(start + len, [...parts, seg]); } }; bt(0, []); return res;}