#93复原 IP 地址

import java.util.ArrayList;
import java.util.List;

final class Solution {
    public List<String> restoreIpAddresses(String s) {
        // 路径保存已确定的段，index 指向下一段的起始字符。
        // 剩余字符数必须落在“剩余段数到其三倍”之间，否则立即剪枝。
        // 多位段禁止前导零，段值超过 255 后继续扩展只会更大。
        // 只有恰好切满四段并消费全部字符时才收集答案。
        List<String> result = new ArrayList<>();
        if (s.length() < 4 || s.length() > 12) {
            return result;
        }
        backtrack(s, 0, new ArrayList<>(4), result);
        return result;
    }

    private void backtrack(String s, int index, List<String> segments, List<String> result) {
        int segmentsLeft = 4 - segments.size();
        int charactersLeft = s.length() - index;
        if (charactersLeft < segmentsLeft || charactersLeft > segmentsLeft * 3) {
            return;
        }
        if (segmentsLeft == 0) {
            result.add(String.join(".", segments));
            return;
        }

        int value = 0;
        for (int end = index; end < s.length() && end < index + 3; end++) {
            if (end > index && s.charAt(index) == '0') {
                break;
            }
            value = value * 10 + (s.charAt(end) - '0');
            if (value > 255) {
                break;
            }
            segments.add(s.substring(index, end + 1));
            backtrack(s, end + 1, segments, result);
            segments.remove(segments.size() - 1);
        }
    }
}