Recover IP addresses from a digit string

You are in a Facebook phone screen and the interviewer asks you to take a string of digits and reconstruct all possible IPv4 addresses from it. No dots are given, just raw digits like "25525511135". Your job is to figure out where the dots belong. This problem, also known as "Restore IP Addresses" on other platforms, is a clean test of backtracking and constraint reasoning. It shows up regularly at companies like Facebook, Amazon, and Oracle.

TL;DR

Use depth-first search to try placing dots at every valid position. At each step, take the next 1, 2, or 3 characters as a byte candidate. Validate that the byte is in the range [0, 255] with no leading zeros. When you have placed all 3 dots and consumed the entire string, you have a valid IP address. Because IPv4 addresses are bounded to 4 bytes of 1-3 digits each, both time and space complexity are O(1).

Why This Problem Matters

IP address recovery sits at the intersection of string partitioning and backtracking, two skills that transfer directly to problems like palindrome partitioning, word break, and phone number letter combinations. The bounded search space makes it a great warm-up for harder backtracking problems, and the constraint validation (no leading zeros, 0-255 range) adds just enough edge-case reasoning to separate careful thinkers from hasty coders.

IPv4 Addresses: The Basics

An IPv4 address consists of exactly four bytes separated by dots. Each byte is a decimal integer between 0 and 255. For example, 192.168.20.40 breaks down into four bytes:

The constraints that matter for this problem:

• Each byte is 1 to 3 digits long
• The numeric value must be between 0 and 255 (inclusive)
• No leading zeros: "01" is invalid, but "0" is fine
• The total input length is between 4 and 12 characters

Understanding the Problem

Given: A string of digits (4-12 characters) Return: All valid IPv4 addresses that can be formed using every digit in the string

Here are a few examples:

genIpAddresses("1010")         -> ["1.0.1.0"]
genIpAddresses("25525511135")  -> ["255.255.11.135", "255.255.111.35"]
genIpAddresses("0000")         -> ["0.0.0.0"]

The core challenge is deciding where to place the three dots. Each placement produces a different partition of the string into four segments, and each segment must be a valid byte.

Edge Cases

1. All zeros ("0000"): The only valid result is "0.0.0.0"
2. Maximum values ("255255255255"): Results in "255.255.255.255"
3. Leading zeros: "010010" cannot produce "01.0.01.0" because "01" is invalid
4. Too few digits: A 4-character string has exactly one way to partition (one digit per byte)

Byte Validation

Before diving into the search algorithm, we need a helper that decides whether a candidate substring is a valid byte. This is the gatekeeper for our DFS traversal.

The validation rules are straightforward:

1. Parse the string to an integer
2. Reject if the value is outside [0, 255]
3. Reject if the string has more than one character and starts with '0'

private boolean isValidByte(String candidate) {
    int intValue = Integer.parseInt(candidate);
    return (!(candidate.length() > 1 && candidate.charAt(0) == '0')) &&
             intValue >= 0 &&
             intValue <= 255;
}

Solution Approach: DFS with Backtracking

The strategy is to build the IP address one byte at a time, exploring all valid choices at each position. Think of it as a decision tree where each level represents choosing the next byte.

Prefer a different language? Jump to solutions in other languages.

For the input "1010", the decision tree looks like this:

At each node, we try taking 1, 2, or 3 characters as the next byte. Branches that fail validation (leading zeros, values over 255, or running out of characters) are pruned. Only paths that consume all characters with exactly 4 bytes reach a valid leaf.

The Recursive Framework

The DFS helper tracks five pieces of state:

• input: the original digit string
• stringSoFar: the IP address being constructed
• index: current position in the input
• dotsRemaining: how many dots we still need to place (starts at 3)
• out: the result set collecting valid addresses

The base cases are:

1. Prune: If index exceeds the string length or dotsRemaining drops below 0, abandon this path
2. Collect: If dotsRemaining is 0 and index equals the string length, we have a valid address

The recursive case tries the next 1, 2, or 3 characters as a byte. For each valid candidate, we recurse with the updated string, incremented index, and decremented dot count.

Tracing Through "1010"

Here is one successful path through the recursion:

The algorithm starts at index 0 with 3 dots remaining. It picks "1" as the first byte (dots stay at 3 because the first byte does not consume a dot). Then it picks "0", "1", and "0" for the remaining bytes. When dotsRemaining hits 0 and index reaches 4, we know "1.0.1.0" is valid and add it to the result set.

Tracing Through "25525511135"

For a longer input, the tree has more branches but most are pruned early:

Starting with "255" as the first byte leads to the two valid results. Branches starting with "2" or "25" eventually fail because the remaining characters cannot form three valid bytes that consume the entire string.

Implementation

Here is the complete Java solution with the DFS helper and byte validator:

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

public class Solution {
  public Set<String> genIpAddresses(String input) {
    Set<String> out = new HashSet<>();
    depthFirstBuild(input, "", 0, 3, out);
    return out;
  }

  private void depthFirstBuild(
    String input,
    String stringSoFar,
    int index,
    int dotsRemaining,
    Set<String> out
  ) {
    if (index > input.length() || dotsRemaining < 0) return;
    else if (dotsRemaining == 0 && index == input.length())
      out.add(stringSoFar);
    else Stream.of(1, 2, 3)
           .filter(i -> i + index <= input.length())
           .map(endIndex -> input.substring(index, index + endIndex))
           .filter(this::isValidByte)
           .forEach(s -> depthFirstBuild(
             input,
             stringSoFar.isEmpty() ? s : String.join(".", stringSoFar, s),
             index + s.length(),
             stringSoFar.isEmpty() ? dotsRemaining : dotsRemaining - 1,
             out)
           );
  }

  private boolean isValidByte(String candidate) {
    int intValue = Integer.parseInt(candidate);
    return (!(candidate.length() > 1 && candidate.charAt(0) == '0')) &&
             intValue >= 0 &&
             intValue <= 255;
  }
}

A few things worth noting about this implementation:

• Stream-based branching: Stream.of(1, 2, 3) generates the three possible byte lengths. The filter and map operations handle bounds checking and substring extraction cleanly.
• Dot tracking: The first byte does not consume a dot (we start with dotsRemaining = 3 and only decrement after the first byte is set). This is handled by checking stringSoFar.isEmpty().
• String.join: Builds the dotted address incrementally without manual string concatenation.

Complexity Analysis

Time Complexity: O(1)

This might surprise you, but the time complexity is constant. An IPv4 address has exactly 4 bytes, each 1-3 digits long. The input is capped at 12 characters. The maximum number of recursive calls is bounded by 3^4 = 81 (three choices per byte, four bytes), and each call does constant work. No matter what input you provide (within the 4-12 character constraint), the algorithm performs a bounded amount of work.

Space Complexity: O(1)

The recursion depth is at most 4 (one level per byte). The output set contains at most a constant number of valid addresses (the maximum for a 12-character input is small). Both the call stack and the result set are bounded by constants.

Common Pitfalls

1. Forgetting leading zero validation: The string "010" is not a valid byte even though 10 is in range. Always check whether a multi-character candidate starts with '0'.

2. Off-by-one on dot counting: The first byte does not consume a dot. If you decrement dotsRemaining for every byte including the first, you will end up requiring 5 segments instead of 4.

3. Not using all characters: A valid address must consume every character in the input. If your base case does not verify index == input.length(), you will generate partial matches.

4. Returning a List instead of a Set: While duplicates are unlikely with correct index tracking, using a Set matches the problem specification and protects against edge cases.

Interview Tips

When solving this problem in an interview:

1. Start by clarifying the constraints: "The input has 4-12 digits, and I need to return all valid IPv4 addresses using every digit?"

2. Sketch the decision tree: Draw how the first few bytes branch for a short input like "1010". This demonstrates your understanding of the search space.

3. Write the byte validator first: It is a clean, testable helper. Getting it right before tackling the DFS shows structured thinking.

4. Discuss the constant complexity: Interviewers often expect candidates to recognize that the bounded input size makes this O(1). It shows you understand the difference between theoretical and practical complexity.

5. Mention the iterative alternative: Three nested loops placing dots at positions i, j, k in the string also work. It is less elegant but sometimes easier to reason about during a live interview.

Key Takeaways

• DFS with backtracking naturally handles the "try all valid partitions" structure of this problem. Each recursive call represents a byte choice, and pruning invalid candidates keeps the search space small.
• The byte validator (no leading zeros, value in [0, 255]) is the critical correctness component. Get it wrong and your DFS will produce garbage results.
• Both time and space complexity are O(1) because IPv4 addresses have a fixed structure: exactly 4 bytes of 1-3 digits each, with input capped at 12 characters.
• This same DFS partitioning pattern shows up in palindrome partitioning, word break, and other string segmentation problems. The input bounds change, but the recursive structure remains the same.
• In interviews, always verify your base case checks both that all dots are placed AND that all characters are consumed. Missing either check is the most common source of bugs.

Solutions in Other Languages

Python

class Solution:
    def gen_ip_addresses(self, input_str):
        out = set()
        self.depth_first_build(input_str, "", 0, 3, out)
        return out

    def depth_first_build(self, input_str, string_so_far, index, dots_remaining, out):
        if index > len(input_str) or dots_remaining < 0:
            return
        elif dots_remaining == 0 and index == len(input_str):
            out.add(string_so_far)
        else:
            for i in range(1, 4):
                if i + index <= len(input_str):
                    substring = input_str[index:index + i]
                    if self.is_valid_byte(substring):
                        if len(string_so_far) == 0:
                            next_string = substring
                            next_dots = dots_remaining
                        else:
                            next_string = ".".join([string_so_far, substring])
                            next_dots = dots_remaining - 1
                        self.depth_first_build(input_str, next_string, index + len(substring), next_dots, out)

    def is_valid_byte(self, candidate):
        return not ((len(candidate) > 1 and candidate[0] == '0') or
                    int(candidate) < 0 or int(candidate) > 255)

JavaScript

class Solution {
  genIpAddresses(input) {
    const out = new Set();
    this.depthFirstBuild(input, "", 0, 3, out);
    return out;
  }

  depthFirstBuild(input, stringSoFar, index, dotsRemaining, out) {
    if (index > input.length || dotsRemaining < 0) return;
    else if (dotsRemaining === 0 && index === input.length) out.add(stringSoFar);
    else [1, 2, 3].filter(i => i + index <= input.length)
        .map(endIndex => input.substring(index, index + endIndex))
        .filter(this.isValidByte)
        .forEach(s => this.depthFirstBuild(input,
          stringSoFar.length === 0 ? s : [stringSoFar, s].join("."),
          index + s.length,
          stringSoFar.length === 0 ? dotsRemaining : dotsRemaining - 1,
          out)
        );
  }

  isValidByte(candidate) {
    const intValue = parseInt(candidate, 10);
    return (!(candidate.length > 1 && candidate.charAt(0) === '0')) &&
      intValue >= 0 && intValue <= 255;
  }
}

TypeScript

class Solution {
  genIpAddresses(input: string): Set<string> {
    const out = new Set<string>();
    this.depthFirstBuild(input, "", 0, 3, out);
    return out;
  }

  depthFirstBuild(input: string, stringSoFar: string, index: number, dotsRemaining: number, out: Set<string>): void {
    if (index > input.length || dotsRemaining < 0) return;
    else if (dotsRemaining === 0 && index === input.length) out.add(stringSoFar);
    else [1, 2, 3].filter(i => i + index <= input.length)
        .map(endIndex => input.substring(index, index + endIndex))
        .filter(this.isValidByte)
        .forEach(s => this.depthFirstBuild(input,
          stringSoFar.length === 0 ? s : [stringSoFar, s].join("."),
          index + s.length,
          stringSoFar.length === 0 ? dotsRemaining : dotsRemaining - 1,
          out)
        );
  }

  isValidByte(candidate: string): boolean {
    const intValue = parseInt(candidate, 10);
    return (!(candidate.length > 1 && candidate.charAt(0) === '0')) &&
      intValue >= 0 && intValue <= 255;
  }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>

class Solution {
public:
  std::unordered_set<std::string> genIpAddresses(const std::string &input) {
    std::unordered_set<std::string> out;
    depthFirstBuild(input, "", 0, 3, out);
    return out;
  }

private:
  bool isValidByte(const std::string &candidate) {
    int intValue = stoi(candidate);
    return !(candidate.size() > 1 && candidate[0] == '0') &&
           intValue >= 0 && intValue <= 255;
  }

  void depthFirstBuild(
      const std::string &input,
      std::string stringSoFar,
      int index,
      int dotsRemaining,
      std::unordered_set<std::string> &out
  ) {
    if (index > input.size() || dotsRemaining < 0) return;
    else if (dotsRemaining == 0 && index == input.size()) {
      out.insert(stringSoFar);
    } else {
      for (int i = 1; i <= 3; ++i) {
        if (i + index <= input.size()) {
          std::string s = input.substr(index, i);
          if (isValidByte(s)) {
            std::string nextStringSoFar = s;
            int nextDotsRemaining = dotsRemaining;
            if (!stringSoFar.empty()) {
              nextStringSoFar = stringSoFar + "." + s;
              nextDotsRemaining = dotsRemaining - 1;
            }
            depthFirstBuild(input, nextStringSoFar, index + s.size(), nextDotsRemaining, out);
          }
        }
      }
    }
  }
};

Scala

import scala.collection.mutable

class Solution {
  def genIpAddresses(input: String): Set[String] = {
    val out = mutable.Set[String]()
    depthFirstBuild(input, "", 0, 3, out)
    out.toSet
  }

  private def depthFirstBuild(
    input: String, stringSoFar: String, index: Int,
    dotsRemaining: Int, out: mutable.Set[String]
  ): Unit = {
    if (index > input.length || dotsRemaining < 0) return
    else if ((dotsRemaining == 0) && (index == input.length)) out.add(stringSoFar)
    else {
      Seq(1, 2, 3)
        .filter(_ + index <= input.length())
        .map(endIndex => input.substring(index, index + endIndex))
        .filter(isValidByte)
        .foreach { s =>
          depthFirstBuild(
            input,
            if (stringSoFar.isEmpty) s else String.join(".", stringSoFar, s),
            index + s.length(),
            if (stringSoFar.isEmpty) dotsRemaining else dotsRemaining - 1,
            out
          )
        }
    }
  }

  private def isValidByte(candidate: String) = {
    val intValue = candidate.toInt
    (!(candidate.length > 1 && candidate.charAt(0) == '0')) &&
      intValue >= 0 && intValue <= 255
  }
}

Kotlin

class Solution {
  fun genIpAddresses(input: String): Set<String> {
    val result = mutableSetOf<String>()
    depthFirstBuild(input, "", 0, 3, result)
    return result
  }

  private fun depthFirstBuild(
    input: String, stringSoFar: String, index: Int,
    dotsRemaining: Int, result: MutableSet<String>
  ) {
    if (index > input.length || dotsRemaining < 0) return
    else if (dotsRemaining == 0 && index == input.length)
      result.add(stringSoFar)
    else (1..3)
           .filter { it + index <= input.length }
           .map { input.substring(index, index + it) }
           .filter { isValidByte(it) }
           .forEach { segment ->
             depthFirstBuild(
               input,
               if (stringSoFar.isEmpty()) segment else "$stringSoFar.$segment",
               index + segment.length,
               if (stringSoFar.isEmpty()) dotsRemaining else dotsRemaining - 1,
               result
             )
           }
  }

  private fun isValidByte(candidate: String): Boolean {
    val intValue = candidate.toInt()
    return !(candidate.length > 1 && candidate[0] == '0') &&
           intValue in 0..255
  }
}

Swift

import Foundation

class Solution {
    func genIpAddresses(_ input: String) -> Set<String> {
        var result = Set<String>()
        depthFirstBuild(input, "", 0, 3, &result)
        return result
    }

    private func depthFirstBuild(
        _ input: String, _ stringSoFar: String, _ index: Int,
        _ dotsRemaining: Int, _ result: inout Set<String>
    ) {
        let chars = Array(input)
        if index > chars.count || dotsRemaining < 0 { return }
        else if dotsRemaining == 0 && index == chars.count {
            result.insert(stringSoFar)
        } else {
            for length in 1...3 {
                if index + length <= chars.count {
                    let segment = String(chars[index..<index + length])
                    if isValidByte(segment) {
                        let nextString = stringSoFar.isEmpty ? segment : "\(stringSoFar).\(segment)"
                        let nextDots = stringSoFar.isEmpty ? dotsRemaining : dotsRemaining - 1
                        depthFirstBuild(input, nextString, index + length, nextDots, &result)
                    }
                }
            }
        }
    }

    private func isValidByte(_ candidate: String) -> Bool {
        guard let intValue = Int(candidate) else { return false }
        return !(candidate.count > 1 && candidate.first == "0") &&
               intValue >= 0 && intValue <= 255
    }
}

Ruby

require 'set'

class Solution
  def gen_ip_addresses(input)
    out = Set.new
    depth_first_build(input, '', 0, 3, out)
    out
  end

  def depth_first_build(input, string_so_far, index, dots_remaining, out)
    return if index > input.length || dots_remaining < 0
    if dots_remaining.zero? && index == input.length
      out.add(string_so_far)
    else
      [1, 2, 3].select { |len| index + len <= input.length }
               .map { |len| input[index, len] }
               .select { |s| valid_byte?(s) }
               .each do |s|
                 new_string = string_so_far.empty? ? s : [string_so_far, s].join('.')
                 new_dots = string_so_far.empty? ? dots_remaining : dots_remaining - 1
                 depth_first_build(input, new_string, index + s.length, new_dots, out)
               end
    end
  end

  def valid_byte?(candidate)
    int_value = candidate.to_i
    !(candidate.length > 1 && candidate[0] == '0') &&
      int_value >= 0 && int_value <= 255
  end
end

Rust

use std::collections::HashSet;

pub struct Solution;

impl Solution {
    pub fn gen_ip_addresses(&self, input: String) -> HashSet<String> {
        let mut out: HashSet<String> = HashSet::new();
        self.depth_first_build(&input, &String::new(), 0, 3, &mut out);
        out
    }

    fn depth_first_build(
        &self, input: &str, string_so_far: &str,
        index: usize, dots_remaining: i32, out: &mut HashSet<String>,
    ) {
        if index > input.len() || dots_remaining < 0 { return; }
        else if dots_remaining == 0 && index == input.len() {
            out.insert(string_so_far.to_string());
        } else {
            for length in 1..=3 {
                if index + length <= input.len() {
                    let segment = &input[index..index + length];
                    if self.is_valid_byte(segment) {
                        let next_string = if string_so_far.is_empty() {
                            segment.to_string()
                        } else {
                            format!("{}.{}", string_so_far, segment)
                        };
                        let next_dots = if string_so_far.is_empty() {
                            dots_remaining
                        } else {
                            dots_remaining - 1
                        };
                        self.depth_first_build(input, &next_string, index + length, next_dots, out);
                    }
                }
            }
        }
    }

    fn is_valid_byte(&self, candidate: &str) -> bool {
        let int_value: i32 = candidate.parse().unwrap_or(-1);
        !(candidate.len() > 1 && candidate.starts_with('0'))
            && int_value >= 0 && int_value <= 255
    }
}

C#

using System.Collections.Generic;
using System.Linq;

public class Solution {
    public HashSet<string> GenIpAddresses(string input) {
        var result = new HashSet<string>();
        DepthFirstBuild(input, "", 0, 3, result);
        return result;
    }

    private void DepthFirstBuild(
        string input, string stringSoFar, int index,
        int dotsRemaining, HashSet<string> result
    ) {
        if (index > input.Length || dotsRemaining < 0) return;
        else if (dotsRemaining == 0 && index == input.Length)
            result.Add(stringSoFar);
        else Enumerable.Range(1, 3)
               .Where(i => i + index <= input.Length)
               .Select(i => input.Substring(index, i))
               .Where(IsValidByte)
               .ToList()
               .ForEach(segment =>
                   DepthFirstBuild(
                       input,
                       stringSoFar.Length == 0 ? segment : string.Join(".", stringSoFar, segment),
                       index + segment.Length,
                       stringSoFar.Length == 0 ? dotsRemaining : dotsRemaining - 1,
                       result
                   )
               );
    }

    private bool IsValidByte(string candidate) {
        int intValue = int.Parse(candidate);
        return !(candidate.Length > 1 && candidate[0] == '0') &&
               intValue >= 0 && intValue <= 255;
    }
}

Dart

class Solution {
  Set<String> genIpAddresses(String input) {
    Set<String> out = {};
    _depthFirstBuild(input, "", 0, 3, out);
    return out;
  }

  void _depthFirstBuild(
    String input, String stringSoFar, int index,
    int dotsRemaining, Set<String> out,
  ) {
    if (index > input.length || dotsRemaining < 0) return;
    else if (dotsRemaining == 0 && index == input.length)
      out.add(stringSoFar);
    else {
      for (int len in [1, 2, 3]) {
        if (index + len <= input.length) {
          String segment = input.substring(index, index + len);
          if (_isValidByte(segment)) {
            _depthFirstBuild(
              input,
              stringSoFar.isEmpty ? segment : "$stringSoFar.$segment",
              index + segment.length,
              stringSoFar.isEmpty ? dotsRemaining : dotsRemaining - 1,
              out,
            );
          }
        }
      }
    }
  }

  bool _isValidByte(String candidate) {
    int intValue = int.parse(candidate);
    return !(candidate.length > 1 && candidate[0] == '0') &&
           intValue >= 0 && intValue <= 255;
  }
}

PHP

<?php

class Solution {
    public function genIpAddresses(string $input): array {
        $out = [];
        $this->depthFirstBuild($input, "", 0, 3, $out);
        return $out;
    }

    private function depthFirstBuild(
        string $input, string $stringSoFar, int $index,
        int $dotsRemaining, array &$out
    ): void {
        if ($index > strlen($input) || $dotsRemaining < 0) return;
        elseif ($dotsRemaining === 0 && $index === strlen($input))
            $out[] = $stringSoFar;
        else {
            $inputLen = strlen($input);
            foreach ([1, 2, 3] as $len) {
                $endIndex = $index + $len;
                if ($endIndex <= $inputLen) {
                    $segment = substr($input, $index, $len);
                    if ($this->isValidByte($segment)) {
                        $this->depthFirstBuild(
                            $input,
                            $stringSoFar === "" ? $segment : $stringSoFar . "." . $segment,
                            $endIndex,
                            $stringSoFar === "" ? $dotsRemaining : $dotsRemaining - 1,
                            $out
                        );
                    }
                }
            }
        }
    }

    private function isValidByte(string $candidate): bool {
        $intValue = intval($candidate);
        return !(strlen($candidate) > 1 && $candidate[0] === '0') &&
               $intValue >= 0 && $intValue <= 255;
    }
}

Practice and Related Problems

If you found this problem interesting, these related problems use similar backtracking patterns:

• Generate combinations of parentheses (problem 61)
• Recursive string permutations (problem 95)
• Phone keypad letter combinations (problem 164)
• Sentence formation with word dictionary (problem 287)

All of these involve partitioning or generating strings under constraints, and the DFS structure carries over directly.

Ready to practice? This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. The spaced repetition system helps you retain these patterns long-term, so when backtracking shows up in your next interview, the solution comes naturally.