Restore IP Addresses

if (seg[0] == '0' and l > 1) or int(seg) > 255:

Check if the segment has a leading zero or exceeds 255.

This line is the critical pruning step that enforces IP address validity rules: segments cannot have leading zeros unless they are exactly '0', and must be ≤ 255. Without this check, invalid IPs would be generated, and the algorithm would waste time exploring invalid paths.

path.pop()

Remove the last segment from the path to backtrack.

This line is the single most critical line in the backtracking algorithm; it restores the path state after recursion returns, enabling exploration of alternative branches without corrupting shared state.

if i == len(s):

Check if the entire string has been consumed when four segments are formed.

Only if the entire string is used up do we have a valid IP address; partial consumption means invalid segmentation.

dfs(i + l)

Recursively call dfs to build the next segment starting after the current segment.

This recursive call is the core of the backtracking algorithm, advancing the exploration by building the next segment from the updated index, enabling exhaustive search of all valid IP addresses.

if len(path) == 4:

Check if four segments have been formed.

An IP address must have exactly four segments; this condition identifies when a complete candidate is ready for validation.

return

Return from recursion after processing four segments.

Stopping recursion here prevents exploring invalid paths with more than four segments, maintaining correctness.

if i + l > len(s):

Break the loop if the segment exceeds the string length.

Preventing out-of-bounds slicing ensures safe substring extraction and avoids runtime errors.

continue

Skip invalid segments and continue to next iteration.

Continuing after invalid segment detection prevents further recursion down invalid paths, improving efficiency and correctness.

res.append(".".join(path))

Add the current valid IP address to the results by joining segments with dots.

Joining the segments into the standard IP address format and adding to results records a valid solution found by the recursion.

for l in range(1, 4):

Iterate over possible segment lengths from 1 to 3.

IP segments can be at most three digits; this loop tries all valid segment lengths from the current index.

seg = s[i:i+l]

Extract the current segment substring from the string.

Capturing the candidate segment allows validation and recursive exploration of this choice.

path.append(seg)

Add the valid segment to the current path.

Appending the segment to the path represents choosing this segment in the current recursive branch, enabling incremental construction of the IP address.

def dfs(i):

Define the recursive DFS function to build IP segments starting from index i.

Encapsulating the backtracking logic in a helper function allows clean recursive exploration of all segmentations from any position in the string.

break

Exit the loop early when segment length is invalid due to string length.

Breaking early avoids unnecessary iterations once the substring would be invalid, improving efficiency.

dfs(0)

Start the backtracking process from index 0.

Initiating the recursion from the start of the string triggers the entire search for valid IP addresses.

path = []

Initialize the current path list to store segments during recursion.

The path list holds the segments of the IP address currently being constructed, enabling incremental building and backtracking.

return res

Return the list of all valid IP addresses found.

Returning the accumulated results provides the final output of the algorithm after exhaustive search.

res = []

Initialize the list to store valid IP addresses.

This list accumulates all valid IP addresses found during the backtracking process, serving as the final output container.