Restore IP Addresses solution and explanation

def restore_ip_addresses(s):
    def backtrack(start, parts):
        if len(parts) == 4:
            if start == len(s):
                result.append(".".join(parts))
            return
        
        for i in range(1, 4):
            if start + i > len(s):
                break
            part = s[start:start+i]
            if (len(part) > 1 and part[0] == '0') or (int(part) > 255):
                continue
            backtrack(start + i, parts + [part])

    result = []
    backtrack(0, [])
    return result

# Example usage:
# restore_ip_addresses("25525511135")

import java.util.*;

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

    private void backtrack(List<String> result, List<String> temp, String s, int start) {
        if (temp.size() == 4) {
            if (start == s.length()) {
                result.add(String.join(".", temp));
            }
            return;
        }

        for (int len = 1; len <= 3; len++) {
            if (start + len > s.length()) break;
            String part = s.substring(start, start + len);
            if ((part.startsWith("0") && part.length() > 1) || Integer.parseInt(part) > 255) continue;
            temp.add(part);
            backtrack(result, temp, s, start + len);
            temp.remove(temp.size() - 1);
        }
    }

    public static void main(String[] args) {
        RestoreIPAddresses rip = new RestoreIPAddresses();
        System.out.println(rip.restoreIpAddresses("25525511135"));
    }
}

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<string> restoreIpAddresses(string s) {
    vector<string> result;
    int n = s.size();
    for (int i = 1; i < 4 && i < n - 2; ++i) {
        for (int j = i + 1; j < i + 4 && j < n - 1; ++j) {
            for (int k = j + 1; k < j + 4 && k < n; ++k) {
                string s1 = s.substr(0, i);
                string s2 = s.substr(i, j - i);
                string s3 = s.substr(j, k - j);
                string s4 = s.substr(k);
                if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                    result.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
                }
            }
        }
    }
    return result;
}

bool isValid(const string &s) {
    if (s.size() > 3 || (s[0] == '0' && s.size() > 1) || stoi(s) > 255) {
        return false;
    }
    return true;
}

int main() {
    vector<string> result = restoreIpAddresses("25525511135");
    for (const string &ip : result) {
        cout << ip << endl;
    }
    return 0;
}

function restoreIpAddresses(s) {
    const result = [];

    for (let i = 1; i < Math.min(4, s.length); ++i) {
        for (let j = i + 1; j < i + Math.min(4, s.length - i); ++j) {
            for (let k = j + 1; k < j + Math.min(4, s.length - j); ++k) {
                if (k < s.length) {
                    const s1 = s.substring(0, i);
                    const s2 = s.substring(i, j);
                    const s3 = s.substring(j, k);
                    const s4 = s.substring(k);

                    if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
                        result.push(`${s1}.${s2}.${s3}.${s4}`);
                    }
                }
            }
        }
    }

    return result;
}

function isValid(segment) {
    return !(segment.length > 3 || (segment[0] === '0' && segment.length > 1) || parseInt(segment, 10) > 255);
}

console.log(restoreIpAddresses('25525511135'));

function restoreIpAddresses(s: string): string[] {
    const n = s.length;
    const ans: string[] = [];
    const t: string[] = [];
    const dfs = (i: number): void => {
        if (i >= n && t.length === 4) {
            ans.push(t.join('.'));
            return;
        }
        if (i >= n || t.length === 4) {
            return;
        }
        let x = 0;
        for (let j = i; j < i + 3 && j < n; ++j) {
            x = x * 10 + s[j].charCodeAt(0) - '0'.charCodeAt(0);
            if (x > 255 || (j > i && s[i] === '0')) {
                break;
            }
            t.push(x.toString());
            dfs(j + 1);
            t.pop();
        }
    };
    dfs(0);
    return ans;
}

public class Solution {
    private IList<string> ans = new List<string>();
    private IList<string> t = new List<string>();
    private int n;
    private string s;

    public IList<string> RestoreIpAddresses(string s) {
        n = s.Length;
        this.s = s;
        dfs(0);
        return ans;
    }

    private void dfs(int i) {
        if (i >= n && t.Count == 4) {
            ans.Add(string.Join(".", t));
            return;
        }
        if (i >= n || t.Count == 4) {
            return;
        }
        int x = 0;
        for (int j = i; j < i + 3 && j < n; ++j) {
            x = x * 10 + (s[j] - '0');
            if (x > 255 || (j > i && s[i] == '0')) {
                break;
            }
            t.Add(x.ToString());
            dfs(j + 1);
            t.RemoveAt(t.Count - 1);
        }
    }
}

func restoreIpAddresses(s string) (ans []string) {
	n := len(s)
	t := []string{}
	var dfs func(int)
	dfs = func(i int) {
		if i >= n && len(t) == 4 {
			ans = append(ans, strings.Join(t, "."))
			return
		}
		if i >= n || len(t) == 4 {
			return
		}
		x := 0
		for j := i; j < i+3 && j < n; j++ {
			x = x*10 + int(s[j]-'0')
			if x > 255 || (j > i && s[i] == '0') {
				break
			}
			t = append(t, s[i:j+1])
			dfs(j + 1)
			t = t[:len(t)-1]
		}
	}
	dfs(0)
	return
}