We're given a string of digits and need to find every way to split it into exactly four parts, where each part is a valid IP address segment: an integer from 0 to 255 with no leading zeros.

A segment can be 1, 2, or 3 digits long, and two rules decide validity. A segment like "01" is invalid because of the leading zero, while "0" by itself is fine. A segment like "256" is invalid because it exceeds 255.

This is a partitioning problem with constraints. We place three dots in the string to divide it into four segments, and every segment must pass the validity check. Since each segment is at most 3 digits and there are always exactly 4 segments, the search space is small. The three dots have at most 3 x 3 x 3 = 27 possible placements.

Key Constraints:

Intuition

We place 3 dots in the string, which creates 4 segments. Three nested loops cover every placement, one loop per dot. The first loop chooses where the first dot goes (after 1, 2, or 3 characters), the second loop chooses the second dot, and the third chooses the third dot. Whatever remains after the third dot becomes the fourth segment.

For each combination, we check whether all four segments are valid. If they are, we record the IP address.

This directly models the problem with no recursion and no extra data structures: try every way to split the string into four parts and keep the valid ones.

Algorithm

Example Walkthrough

Code

The three nested loops are hardcoded for exactly 4 segments and validate each split only after building all four substrings. The next approach expresses the same search recursively, which lets it abandon a branch the moment a partial segment is invalid instead of always running the inner loops to completion.

Instead of three nested loops, we express the search recursively. At each step we choose how many characters to take for the current segment: 1, 2, or 3. If that segment is valid, we recurse to fill the remaining segments from the rest of the string. When we have 4 segments and have consumed the entire string, we record the IP address.

This is backtracking over a decision tree where each node chooses 1, 2, or 3 characters for one segment. We prune a branch as soon as a segment is invalid. If the first segment "00" has a leading zero, every combination starting with it is dropped at once rather than rebuilt and rechecked in inner loops. The brute force, by contrast, only discovers that the split fails after constructing all four substrings.

Algorithm

Example Walkthrough

Code

Both approaches run in constant time because the IP structure fixes the search at no more than 27 dot placements regardless of input length. The brute force is the most direct to write and reason about. The backtracking version generalizes more cleanly (changing 4 to any segment count is a one-line edit) and prunes invalid prefixes before building the rest of the split, so it touches fewer combinations on inputs with many early rejections. For this problem either is a fine answer; backtracking is the more reusable template for the broader family of string-partitioning problems.