Recursion Backtracking Combinatorics
Intermediate Level

Implement the restoreIpAddressesCount method that counts valid IP addresses that can be restored from the digits.

The input is a string digits containing only numeric characters.

Your task is to count how many valid IP addresses can be restored by inserting three dots into the string. A valid IP address has exactly four parts.

Each part must be between 0 and 255. A part cannot have leading zeros unless the part itself is exactly 0.

Example 1
Input:
digits (string) = 25525511135
Return:
(int) 2
Example 2
Input:
digits (string) = 0
Return:
(int) 1
Example 3
Input:
digits (string) = 1111
Return:
(int) 1

Use backtracking to choose four IP address segments.

At each step, try taking one, two, or three digits as the next segment. Accept the segment only if it is within 0 to 255 and does not break the leading-zero rule.

When exactly four segments are chosen and all digits are used, one valid IP address has been restored.

Pseudocode:

function restoreIpAddressesCount(digits):
    count = 0
    backtrack(index, parts):
        if parts == 4:
            if index == length of digits:
                count++
            return
        for length from 1 to 3:
            if index + length > length of digits:
                break
            segment = substring of digits from index with given length
            if segment has leading zero and length > 1:
                continue
            if numeric value of segment > 255:
                continue
            backtrack(index + length, parts + 1)
    backtrack(0, 0)
    return count
Run your code to see the result.