Restore IP Addresses

Given a string s containing only digits, return all possible valid IP addresses that can be formed by inserting dots into s. A valid IP address consists of exactly four integers, each between 0 and 255, separated by dots, and with no leading zeros.

Example 1

Input: s = "25525511135" → Output: ["255.255.11.135","255.255.111.35"]

Example 2

Input: s = "0000" → Output: ["0.0.0.0"]

Solution Approach

Use backtracking: at each step, try taking 1, 2, or 3 characters as the next octet. Validate each segment (no leading zeros, value 0-255). Stop when 4 parts are formed.

Backtrack with parameters: current index in s, list of parts so far.
If parts.size()==4 and idx==s.length(), add joined result.
Try lengths 1, 2, 3 for the next segment; validate each.
Prune if remaining characters cannot form enough (or too many) segments.

Java

import java.util.*;

class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> result = new ArrayList<>();
        backtrack(s, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(String s, int idx, List<String> parts, List<String> result) {
        if (parts.size() == 4) {
            if (idx == s.length()) result.add(String.join(".", parts));
            return;
        }
        int remaining = 4 - parts.size();
        int charsLeft = s.length() - idx;
        if (charsLeft < remaining || charsLeft > remaining * 3) return;

        for (int len = 1; len <= 3 && idx + len <= s.length(); len++) {
            String seg = s.substring(idx, idx + len);
            if (seg.length() > 1 && seg.charAt(0) == '0') break;
            if (Integer.parseInt(seg) > 255) break;
            parts.add(seg);
            backtrack(s, idx + len, parts, result);
            parts.remove(parts.size() - 1);
        }
    }
}

Time Complexity: O(1). At most 3^4 = 81 candidates
Space Complexity: O(1). Constant max parts