Micro-Drill #192 — Restore IP addresses

def restoreIpAddresses(s):
    res = []
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                res.append('.'.join(parts))
            return
        for length in range(1, 4):
            if start + length > len(s): break
            seg = s[start:start+length]
            if (seg[0] == '0' and len(seg) > 1) or int(seg) > 255:
                continue
            backtrack(start + length, parts + [seg])
    backtrack(0, [])
    return res