Restore IP Addresses Visualizer & Step-by-Step Algorithm Solution

Generate all possible valid IPv4 addresses by partitioning a string into four octets (0-255 without leading zeros) using recursive backtracking.

Category: backtracking | Difficulty: Medium

Tags: Backtracking, String, Recursion, Pruning

Restore IP Addresses

[]
Input Digits "25525511135"
2
0
5
1
5
2
2
3
5
4
5
5
1
6
1
7
1
8
3
9
5
10
100%
state
s"25525511135"
curr[]
octets0/4
start-
end-
validIpsFound0
result[]
length11
Initialization
1/452
Explanation

Start restoreIpAddresses on string "25525511135" (length 11).

Source Code
1function restoreIpAddresses(s: string): string[] {
2 const result: string[] = [];
3 function backtrack(curr: string[], start: number) {
4 if (curr.length === 4 && start === s.length) {
5 result.push(curr.join("."));
6 return;
7 }
8
9 if (curr.length === 4 || start === s.length) return;
10
11 for (let end = start; end < s.length; end++) {
12 let str = s.slice(start, end + 1);
13 if (str.length > 3) break;
14 if (Number(str) > 255) break;
15 if (str.length > 1 && str[0] === "0") break;
16 curr.push(str);
17 backtrack(curr, end + 1);
18 curr.pop();
19 }
20 }
21 backtrack([], 0);
22 return result;
23}