class Solution {
    fun restoreIpAddresses(s: String): List<String> {
        val result = mutableListOf<String>()
        val segments = mutableListOf<String>()

        fun backtrack(start: Int) {
            if (segments.size == 4) {
                if (start == s.length) {
                    result.add(segments.joinToString("."))
                }
                return
            }

            for (len in 1..3) {
                if (start + len > s.length) break

                val segment = s.substring(start, start + len)

                // 前導零檢查：長度 > 1 但以 '0' 開頭
                if (segment.length > 1 && segment[0] == '0') break

                // 範圍檢查
                if (segment.toInt() > 255) break

                // 剩餘長度檢查
                val remaining = s.length - start - len
                val segmentsLeft = 3 - segments.size
                if (remaining < segmentsLeft || remaining > segmentsLeft * 3) continue

                segments.add(segment)
                backtrack(start + len)
                segments.removeAt(segments.lastIndex)
            }
        }

        backtrack(0)
        return result
    }
}