字节跳动复原 IP 地址：回溯剪枝到任意 k 段

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 输入只含 ASCII 数字；标准题分四段，每段 1–3 位、数值不大于 255，除单个 0 外不得以 0 开头。
• k 段追问沿用每段 1–3 位、上限 255 的训练规则；真实面试若改了段长或上限，应把它们作为参数重新确认。
• 输出每一种按原数字顺序切分的结果，不改变数字顺序，也不补零。

解题路线

1. 用 DFS 状态 (当前位置, 已选段列表) 逐段尝试 1、2、3 位。每取一段先判前导零与数值上限。
2. 若剩余数字数小于剩余段数，或大于剩余段数的三倍，立即剪枝。
3. 恰好选满 k 段且消费全部数字时才输出；把固定四段改为 k 段只需参数化目标段数，边界仍要一起改。

手动走一遍

输入 25525511135、k=4，可得到 255.255.11.135 和 255.255.111.35。输入 010010 时，01 这类段会因前导零被排除，但单独的 0 保留。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def restore_segments(digits, parts=4, max_value=255):
    """Split digits into numeric parts of length 1..3 without leading zeros."""
    if parts <= 0 or max_value < 0 or not digits.isascii() or not digits.isdigit():
        raise ValueError("invalid input")
    answers = []
    chosen = []

    def search(position):
        remaining_parts = parts - len(chosen)
        remaining_digits = len(digits) - position
        if not remaining_parts <= remaining_digits <= 3 * remaining_parts:
            return
        if remaining_parts == 0:
            answers.append(".".join(chosen))
            return

        for width in (1, 2, 3):
            segment = digits[position:position + width]
            if len(segment) != width:
                break
            if width > 1 and segment[0] == "0":
                break
            if int(segment) > max_value:
                break
            chosen.append(segment)
            search(position + width)
            chosen.pop()

    search(0)
    return answers

复杂度

每层最多三种段长，搜索树上界为 O(3^k)，每个答案拼接需 O(k)；长度剪枝会显著减少实际搜索。输出本身可能有多条，因此空间为 O(k) 递归栈与答案总长度。

易错点与追问

容易失分的边界

• 只检查数值 ≤255 会把 001 当成合法段；前导零要在转整数前判断。
• 切满 k 段却没有耗尽输入，或输入耗尽但尚未切满，都不能输出。
• 任意 k 段并非真正的 IPv4 地址。讲解时应区分原题标准四段与训练扩展。

继续深挖

• 如果只需计数而非列出所有切分，可以用 (position, remaining_parts) 做记忆化搜索。
• 若每段最大长度为 L、上限为 M，剪枝上界改成 L×剩余段数，合法性检查仍由参数控制。