Problem Statement

Restore IP Addresses

You are given a string s made only of digits, like "25525511135". Your job is to find every valid IP address you can make by slipping three dots into that string. An IP address is four numbers separated by dots, like 255.255.11.135. Each number, called a segment, has to follow two rules: it must be between 0 and 255, and it cannot have a leading zero (so "01" or "00" is not allowed, but plain "0" is fine). To solve this, we use backtracking. Backtracking means we try one choice, go deeper to see where it leads, and if it does not work out we undo that choice and try the next one. Think of walking a maze: you pick a path, and if you hit a dead end you back up to the last fork and try a different turn. Here, each "choice" is how many digits to grab for the next segment, 1, 2, or 3. Because an IP address always has exactly 4 segments and each segment is short, there are not many paths to try, so the work stays small.

mediumBacktrackingStringBacktrackingTime: O(1) · Space: O(1)

Signals to notice

split string into 4 valid IP segments1-3 digits per segment0-255 no leading zeros

Brute force first

Try all 3 split points — O(n³).

The key insight

Backtracking: take 1-3 digits, validate (0-255, no leading zeros), recurse. 4 segments must consume all characters. O(1) since input ≤ 12 chars.

Trace it on `s="101023"`

backtrack(0,[]): try len1 seg="1" -> recurse start=1, segments=["1"]
["1","0"] at start=2: seg="10" -> ["1","0","10"] start=4, then "23" consumes all -> record "1.0.10.23"; seg="102" -> ["1","0","102"], "3" all -> record "1.0.102.3"
["1"] try len2 "01": leading zero -> break this branch
["10"] at start=2: "1"->["10","1","0"] then "23" -> record "10.1.0.23"; "10"->["10","10","2"] then "3" -> record "10.10.2.3"; "102"->"3" leaves only 3 segs at end -> dead
["101"] at start=3: "0"->["101","0","2"] then "3" -> record "101.0.2.3"
len4 seg="1010" exceeds 3 digits / start+len>len(s) bounds -> loop ends, backtrack unwinds
return ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

What must stay true

Each segment: 1-3 digits, value 0-255, no leading zeros (except '0' alone). Exactly 4 segments consuming the full string.

Shape of the loop

backtrack(start, segments):
  if len(segments)==4 and start==len(s): record '.'.join(segments); return
  if len(segments)==4 or start==len(s): return
  for length in 1..3:
    if start + length > len(s): break          # stay in bounds
    seg = s[start:start+length]
    if leadingZero(seg) or int(seg) > 255: break
    backtrack(start+length, segments+[seg])     # then pop

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Allowing '01' — only '0' is valid as a leading-zero segment.

Backtracking Pattern