Restore IP Addresses

def restore_ip_addresses(s):
    res = []
    def go(i, parts):
        left = 4 - len(parts)
        if not left <= len(s) - i <= 3 * left:
            return
        if left == 0:
            res.append('.'.join(parts))
            return
        for k in range(1, 4):
            part = s[i:i + k]
            if len(part) < k or (k > 1 and part[0] == '0') or int(part) > 255:
                break
            go(i + k, parts + [part])
    go(0, [])
    return res

Restore IP Addresses. Given a string of digits, insert three dots to form every valid IP address: four parts, each zero to two fifty-five, no leading zeros, every digit used in order.

Two five five two five five one one one three five gives two addresses. Four zeros gives just zero dot zero dot zero dot zero. One zero one zero two three gives five.

The naive way: try every spot for the three dots, then check each address. Eleven digits leave ten gaps, so one hundred twenty tries, and only two pass. Fine here, but backtracking prunes most of them early.

The key idea: build one part at a time. Take one, two or three digits. Skip a part with a leading zero, or over two fifty-five. Prune when the digits left can't fill the parts left, one to three digits each. When four parts use every digit, record the address.

In code, the fit check comes first; with no parts left, it needs no digits left. Then try each length, and stop at a bad part.

Now the first example. A first part of two leaves ten digits for three parts: pruned. Twenty-five lasts one level, then every cut fails. Two fifty-five survives, twice. Then eleven and one thirty-five, or one eleven and thirty-five: two addresses.

At most three lengths for each of four parts: eighty-one paths at most. Valid input has twelve digits at most, so time and space are constant.

Cut up to three digits, skip bad parts, prune what can't fit. That's Restore IP Addresses.