Restore IP Addresses

🎯

Restore IP Addresses

mediumBACKTRACKINGAmazonFacebookGoogle

Imagine you receive a string of digits from a network packet, but the dots separating the IP address segments are missing. Your task is to restore all possible valid IP addresses from this string.

💡 This problem is about splitting a string into exactly four parts where each part is a valid IP segment. Beginners often struggle because they try to guess the splits without systematically exploring all possibilities and validating each segment carefully.

📋

Problem Statement

Given a string containing only digits, restore all possible valid IP address combinations. A valid IP address consists of exactly four integers (each between 0 and 255) separated by single dots, and no segment should contain leading zeros unless the segment is exactly '0'. Return all possible valid IP addresses in any order.

1 ≤ length of input string ≤ 20Input string contains only digits

💡

Example

Input"\"25525511135\""

Output["255.255.11.135", "255.255.111.35"]

The string can be split into these two valid IP addresses by placing dots at appropriate positions.

• Input string length less than 4 → no valid IP addresses
• Input string length greater than 12 → no valid IP addresses (since max 3 digits per segment and 4 segments)
• Segments with leading zeros like '00' or '01' → invalid
• Segment value greater than 255 → invalid

⚠️

Common Mistakes

Allowing segments with leading zeros like '00' or '01'

Generates invalid IP addresses that do not conform to IP rules

✅ Add explicit check to reject segments starting with '0' unless the segment is exactly '0'

Not checking segment value > 255

Includes invalid IP segments like '256' or '999' in results

✅ Convert segment to integer and reject if > 255

Not pruning based on remaining string length and segments

Causes unnecessary recursion leading to timeouts or inefficiency

✅ Add pruning condition to check if remaining characters fit remaining segments

Adding IP address to results before confirming all 4 segments and full string consumption

Partial or incomplete IP addresses are included in output

✅ Only add to results when exactly 4 segments are formed and entire string is used

Using global variables without resetting between test cases

Results from previous runs contaminate current output

✅ Use local variables or clear global state before each run

🧠

Brute Force (Pure Recursion with Backtracking)

💡 This approach exists to build intuition by exploring all possible ways to split the string into four parts, validating each segment. It helps beginners understand the problem structure before optimizing.

Intuition

Try every possible split of the string into four parts by recursively choosing 1 to 3 digits for each segment, checking if each segment is valid, and backtracking if not.

Algorithm

1. Start from the beginning of the string and try to take 1, 2, or 3 digits as the current segment.
2. Check if the current segment is valid (not leading zero unless single '0', and ≤ 255).
3. If valid, recurse to find the next segment until 4 segments are formed.
4. If 4 segments are formed and the entire string is consumed, add the formed IP address to results.

💡 The challenge is to systematically try all splits and backtrack when a segment is invalid or when the number of segments exceeds four.

</>

Code

from typing import List

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    def backtrack(start: int, path: List[str]):
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            return
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
                continue
            backtrack(start + length, path + [segment])
    backtrack(0, [])
    return res

# Driver code
if __name__ == "__main__":
    test_input = "25525511135"
    print(restore_ip_addresses(test_input))

Line Notes

def restore_ip_addresses(s: str) -> List[str]:Defines the main function with input string s and output list of strings

def backtrack(start: int, path: List[str]):Helper recursive function tracking current index and collected segments

if len(path) == 4:Base case: if 4 segments collected, check if entire string is used

if start == len(s):Only add to results if all characters are consumed

for length in range(1, 4):Try segments of length 1 to 3

if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):Prune invalid segments early

backtrack(start + length, path + [segment])Recurse with updated start and path

return resReturn all valid IP addresses found

import java.util.*;

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

    private static void backtrack(String s, int start, List<String> path, List<String> res) {
        if (path.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", path));
            }
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > s.length()) break;
            String segment = s.substring(start, start + len);
            if ((segment.startsWith("0") && segment.length() > 1) || (len == 3 && Integer.parseInt(segment) > 255)) continue;
            path.add(segment);
            backtrack(s, start + len, path, res);
            path.remove(path.size() - 1);
        }
    }

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

Line Notes

public static List<String> restoreIpAddresses(String s)Main method signature returning list of valid IPs

backtrack(s, 0, new ArrayList<>(), res);Start recursion from index 0 with empty path

if (path.size() == 4)Check if 4 segments collected

if (start == s.length())Add to results only if entire string consumed

for (int len = 1; len <= 3; len++)Try segments of length 1 to 3

if ((segment.startsWith("0") && segment.length() > 1) || (len == 3 && Integer.parseInt(segment) > 255)) continue;Skip invalid segments

path.add(segment);Choose current segment

path.remove(path.size() - 1);Backtrack by removing last segment

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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> path;
        backtrack(s, 0, path, res);
        return res;
    }

private:
    void backtrack(const string& s, int start, vector<string>& path, vector<string>& res) {
        if (path.size() == 4) {
            if (start == s.size()) {
                string ip = path[0];
                for (int i = 1; i < 4; i++) ip += "." + path[i];
                res.push_back(ip);
            }
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > s.size()) break;
            string segment = s.substr(start, len);
            if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;
            path.push_back(segment);
            backtrack(s, start + len, path, res);
            path.pop_back();
        }
    }
};

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

Line Notes

vector<string> restoreIpAddresses(string s)Main function returning vector of valid IPs

void backtrack(const string& s, int start, vector<string>& path, vector<string>& res)Recursive helper with current index and path

if (path.size() == 4)Base case: 4 segments collected

if (start == s.size())Add IP if entire string consumed

for (int len = 1; len <= 3; len++)Try segments of length 1 to 3

if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;Skip invalid segments

path.push_back(segment);Choose segment

path.pop_back();Backtrack by removing last segment

function restoreIpAddresses(s) {
    const res = [];
    function backtrack(start, path) {
        if (path.length === 4) {
            if (start === s.length) {
                res.push(path.join('.'));
            }
            return;
        }
        for (let len = 1; len <= 3; len++) {
            if (start + len > s.length) break;
            const segment = s.substring(start, start + len);
            if ((segment.startsWith('0') && segment.length > 1) || (len === 3 && Number(segment) > 255)) continue;
            backtrack(start + len, [...path, segment]);
        }
    }
    backtrack(0, []);
    return res;
}

// Test
console.log(restoreIpAddresses("25525511135"));

Line Notes

function restoreIpAddresses(s)Main function to restore IP addresses

function backtrack(start, path)Recursive helper tracking index and segments

if (path.length === 4)Check if 4 segments collected

if (start === s.length)Add to results if entire string consumed

for (let len = 1; len <= 3; len++)Try segments of length 1 to 3

if ((segment.startsWith('0') && segment.length > 1) || (len === 3 && Number(segment) > 255)) continue;Skip invalid segments

backtrack(start + len, [...path, segment]);Recurse with new segment added

⏱

Complexity

TimeO(3^4) = O(81)

SpaceO(4) for recursion stack and path

At each of the 4 segments, we try up to 3 lengths, so 3^4 combinations. Each segment validation is O(1).

💡 For n=12 (max length), this means at most 81 recursive calls, which is manageable but not efficient for larger inputs.

Interview Verdict: Accepted but not optimal

This approach works and is easy to understand but can be improved by pruning and iterative methods.

🧠

Backtracking with Early Pruning

💡 This approach improves brute force by adding checks to prune impossible paths early, reducing unnecessary recursion and speeding up the search.

Intuition

Before recursing, check if the remaining string length fits the remaining segments (min 1 char per segment, max 3 chars per segment). If not, prune immediately.

Algorithm

1. At each recursion, check if the remaining characters can fit into the remaining segments (between remaining_segments and 3 * remaining_segments).
2. If not, return immediately to prune the search space.
3. Otherwise, try segments of length 1 to 3, validate, and recurse.
4. Add valid IP addresses to results when 4 segments are formed and string is fully consumed.

💡 The pruning condition is key to reducing the exponential search space by cutting off impossible branches early.

</>

Code

from typing import List

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    def backtrack(start: int, path: List[str]):
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            return
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            return
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
                continue
            backtrack(start + length, path + [segment])
    backtrack(0, [])
    return res

# Driver code
if __name__ == "__main__":
    test_input = "25525511135"
    print(restore_ip_addresses(test_input))

Line Notes

remaining_segments = 4 - len(path)Calculate how many segments are left to fill

remaining_chars = len(s) - startCalculate how many characters remain in the string

if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:Prune if remaining chars can't fit the remaining segments

if len(path) == 4:Check if 4 segments collected

if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):Validate segment early

backtrack(start + length, path + [segment])Recurse with chosen segment

import java.util.*;

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

    private static void backtrack(String s, int start, List<String> path, List<String> res) {
        int remainingSegments = 4 - path.size();
        int remainingChars = s.length() - start;
        if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;
        if (path.size() == 4) {
            if (start == s.length()) {
                res.add(String.join(".", path));
            }
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > s.length()) break;
            String segment = s.substring(start, start + len);
            if ((segment.startsWith("0") && segment.length() > 1) || (len == 3 && Integer.parseInt(segment) > 255)) continue;
            path.add(segment);
            backtrack(s, start + len, path, res);
            path.remove(path.size() - 1);
        }
    }

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

Line Notes

int remainingSegments = 4 - path.size();Calculate remaining segments to fill

int remainingChars = s.length() - start;Calculate remaining characters in string

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;Prune impossible paths early

if (path.size() == 4)Check if 4 segments collected

if ((segment.startsWith("0") && segment.length() > 1) || (len == 3 && Integer.parseInt(segment) > 255)) continue;Validate segment

path.add(segment);Choose segment

path.remove(path.size() - 1);Backtrack

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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        vector<string> path;
        backtrack(s, 0, path, res);
        return res;
    }

private:
    void backtrack(const string& s, int start, vector<string>& path, vector<string>& res) {
        int remainingSegments = 4 - path.size();
        int remainingChars = s.size() - start;
        if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;
        if (path.size() == 4) {
            if (start == s.size()) {
                string ip = path[0];
                for (int i = 1; i < 4; i++) ip += "." + path[i];
                res.push_back(ip);
            }
            return;
        }
        for (int len = 1; len <= 3; len++) {
            if (start + len > s.size()) break;
            string segment = s.substr(start, len);
            if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;
            path.push_back(segment);
            backtrack(s, start + len, path, res);
            path.pop_back();
        }
    }
};

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

Line Notes

int remainingSegments = 4 - path.size();Calculate how many segments left

int remainingChars = s.size() - start;Calculate remaining characters

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;Prune impossible paths

if (path.size() == 4)Check if 4 segments collected

if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;Validate segment

path.push_back(segment);Choose segment

path.pop_back();Backtrack

function restoreIpAddresses(s) {
    const res = [];
    function backtrack(start, path) {
        const remainingSegments = 4 - path.length;
        const remainingChars = s.length - start;
        if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;
        if (path.length === 4) {
            if (start === s.length) {
                res.push(path.join('.'));
            }
            return;
        }
        for (let len = 1; len <= 3; len++) {
            if (start + len > s.length) break;
            const segment = s.substring(start, start + len);
            if ((segment.startsWith('0') && segment.length > 1) || (len === 3 && Number(segment) > 255)) continue;
            backtrack(start + len, [...path, segment]);
        }
    }
    backtrack(0, []);
    return res;
}

// Test
console.log(restoreIpAddresses("25525511135"));

Line Notes

const remainingSegments = 4 - path.length;Calculate remaining segments

const remainingChars = s.length - start;Calculate remaining characters

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) return;Prune impossible paths early

if (path.length === 4)Check if 4 segments collected

if ((segment.startsWith('0') && segment.length > 1) || (len === 3 && Number(segment) > 255)) continue;Validate segment

backtrack(start + len, [...path, segment]);Recurse with chosen segment

⏱

Complexity

TimeO(3^4) but with pruning reduces actual calls

SpaceO(4) recursion stack and path

Pruning reduces the number of recursive calls by eliminating impossible splits early, improving practical runtime.

💡 This pruning makes the algorithm faster in practice, especially for longer strings, by avoiding useless work.

Interview Verdict: Accepted and more efficient than brute force

This approach is preferred in interviews as it balances clarity and efficiency.

🧠

Iterative Backtracking with Stack

💡 This approach uses an explicit stack to simulate recursion, which can help avoid stack overflow and is useful in languages or environments with limited recursion depth.

Intuition

Use a stack to store partial solutions and indices, iteratively exploring all valid segments until four segments are formed or no more splits are possible.

Algorithm

1. Initialize a stack with tuples containing start index, current path, and segment count.
2. While stack not empty, pop the top and try to extend the path by 1 to 3 digit segments.
3. Validate each segment and if valid, push new state onto stack.
4. If 4 segments formed and string fully consumed, add to results.

💡 This approach mimics recursion but uses a loop and stack data structure to manage state explicitly.

</>

Code

from typing import List

def restore_ip_addresses(s: str) -> List[str]:
    res = []
    stack = [(0, [])]  # (start index, path)
    while stack:
        start, path = stack.pop()
        if len(path) == 4:
            if start == len(s):
                res.append(".".join(path))
            continue
        remaining_segments = 4 - len(path)
        remaining_chars = len(s) - start
        if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:
            continue
        for length in range(1, 4):
            if start + length > len(s):
                break
            segment = s[start:start+length]
            if (segment.startswith('0') and len(segment) > 1) or (length == 3 and int(segment) > 255):
                continue
            stack.append((start + length, path + [segment]))
    return res

# Driver code
if __name__ == "__main__":
    test_input = "25525511135"
    print(restore_ip_addresses(test_input))

Line Notes

stack = [(0, [])]Initialize stack with starting index and empty path

while stack:Process states until stack is empty

if len(path) == 4:Check if 4 segments collected

if start == len(s):Add to results if entire string consumed

remaining_segments = 4 - len(path)Calculate remaining segments

if remaining_chars < remaining_segments or remaining_chars > 3 * remaining_segments:Prune impossible states

for length in range(1, 4):Try segments of length 1 to 3

stack.append((start + length, path + [segment]))Push new state onto stack

import java.util.*;

public class RestoreIPAddresses {
    public static List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();
        Deque<State> stack = new ArrayDeque<>();
        stack.push(new State(0, new ArrayList<>()));
        while (!stack.isEmpty()) {
            State curr = stack.pop();
            int start = curr.start;
            List<String> path = curr.path;
            if (path.size() == 4) {
                if (start == s.length()) {
                    res.add(String.join(".", path));
                }
                continue;
            }
            int remainingSegments = 4 - path.size();
            int remainingChars = s.length() - start;
            if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;
            for (int len = 1; len <= 3; len++) {
                if (start + len > s.length()) break;
                String segment = s.substring(start, start + len);
                if ((segment.startsWith("0") && segment.length() > 1) || (len == 3 && Integer.parseInt(segment) > 255)) continue;
                List<String> newPath = new ArrayList<>(path);
                newPath.add(segment);
                stack.push(new State(start + len, newPath));
            }
        }
        return res;
    }

    static class State {
        int start;
        List<String> path;
        State(int start, List<String> path) {
            this.start = start;
            this.path = path;
        }
    }

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

Line Notes

Deque<State> stack = new ArrayDeque<>();Initialize stack to hold states

stack.push(new State(0, new ArrayList<>()));Push initial state with index 0 and empty path

while (!stack.isEmpty())Process states until stack empty

if (path.size() == 4)Check if 4 segments collected

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;Prune impossible states

for (int len = 1; len <= 3; len++)Try segments of length 1 to 3

stack.push(new State(start + len, newPath));Push new state with updated index and path

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

class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        vector<string> res;
        struct State {
            int start;
            vector<string> path;
            State(int st, vector<string> p) : start(st), path(move(p)) {}
        };
        stack<State> stk;
        stk.push(State(0, {}));
        while (!stk.empty()) {
            State curr = stk.top();
            stk.pop();
            int start = curr.start;
            vector<string>& path = curr.path;
            if (path.size() == 4) {
                if (start == s.size()) {
                    string ip = path[0];
                    for (int i = 1; i < 4; i++) ip += "." + path[i];
                    res.push_back(ip);
                }
                continue;
            }
            int remainingSegments = 4 - (int)path.size();
            int remainingChars = (int)s.size() - start;
            if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;
            for (int len = 1; len <= 3; len++) {
                if (start + len > (int)s.size()) break;
                string segment = s.substr(start, len);
                if ((segment[0] == '0' && segment.size() > 1) || (len == 3 && stoi(segment) > 255)) continue;
                vector<string> newPath = path;
                newPath.push_back(segment);
                stk.push(State(start + len, newPath));
            }
        }
        return res;
    }
};

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

Line Notes

struct StateDefines a state with current index and path

stack<State> stk;Stack to hold states for iterative backtracking

stk.push(State(0, {}));Push initial state

if (path.size() == 4)Check if 4 segments collected

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;Prune impossible states

for (int len = 1; len <= 3; len++)Try segments of length 1 to 3

stk.push(State(start + len, newPath));Push new state with updated path

function restoreIpAddresses(s) {
    const res = [];
    const stack = [{ start: 0, path: [] }];
    while (stack.length > 0) {
        const { start, path } = stack.pop();
        if (path.length === 4) {
            if (start === s.length) {
                res.push(path.join('.'));
            }
            continue;
        }
        const remainingSegments = 4 - path.length;
        const remainingChars = s.length - start;
        if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;
        for (let len = 1; len <= 3; len++) {
            if (start + len > s.length) break;
            const segment = s.substring(start, start + len);
            if ((segment.startsWith('0') && segment.length > 1) || (len === 3 && Number(segment) > 255)) continue;
            stack.push({ start: start + len, path: [...path, segment] });
        }
    }
    return res;
}

// Test
console.log(restoreIpAddresses("25525511135"));

Line Notes

const stack = [{ start: 0, path: [] }];Initialize stack with starting state

while (stack.length > 0)Process states until stack empty

if (path.length === 4)Check if 4 segments collected

if (remainingChars < remainingSegments || remainingChars > 3 * remainingSegments) continue;Prune impossible states

for (let len = 1; len <= 3; len++)Try segments of length 1 to 3

stack.push({ start: start + len, path: [...path, segment] });Push new state with updated path

⏱

Complexity

TimeO(3^4) with pruning

SpaceO(4) for stack and path storage

Similar to recursive backtracking but uses explicit stack to avoid recursion overhead and stack overflow.

💡 This iterative approach is useful in environments with recursion limits and helps understand recursion mechanics.

Interview Verdict: Accepted and safe for deep recursion cases

This approach is a good alternative when recursion depth is a concern or iterative solutions are preferred.

📊

All Approaches - One-Glance Tradeoffs

💡 In most interviews, the backtracking with pruning approach is the best balance of clarity and efficiency to implement.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(3^4) = O(81)	O(4) recursion stack	Yes (deep recursion possible but limited here)	Yes	Mention only - never code due to inefficiency
2. Backtracking with Early Pruning	O(3^4) but pruned, faster in practice	O(4) recursion stack	Low	Yes	Code this approach in 95% of interviews
3. Iterative Backtracking with Stack	O(3^4) with pruning	O(4) stack and path storage	No	Yes	Use if recursion depth is a concern or interviewer requests iterative

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach, optimize with pruning, and optionally discuss iterative solutions. Practice coding and testing thoroughly.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force recursive backtracking approach.Step 3: Explain how pruning can reduce the search space.Step 4: Code the optimized backtracking solution.Step 5: Test with edge cases and discuss time/space complexity.Step 6: Optionally mention iterative backtracking if recursion depth is a concern.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your understanding of backtracking, string partitioning, pruning invalid paths, and handling edge cases like leading zeros and segment bounds.

Common Follow-ups

• What if the input string is very long? → Discuss pruning and iterative solutions.
• Can you generate IP addresses in lexicographical order? → Sort results or modify traversal order.

💡 These follow-ups test your ability to optimize and adapt your solution to additional constraints or performance requirements.

🔍

Pattern Recognition

When to Use

Use this pattern when you need to split a string into a fixed number of parts with constraints on each part, and you want to generate all valid combinations.

Signature Phrases

"Restore all possible valid IP addresses""Split string into exactly four parts""Each part must be between 0 and 255""No leading zeros allowed"

NOT This Pattern When

Problems that require only counting partitions or greedy splitting without backtracking are different patterns.

Similar Problems

Generate Parentheses - similar recursive generation with constraintsPalindrome Partitioning - partition string into palindromesLetter Combinations of a Phone Number - combinatorial string generation

Practice

1. Given the following code snippet for getPermutation, what is the returned value when calling getPermutation(3, 3)?

easy

A. '123'

B. '312'

C. '213'

D. '231'

Solution

1. Step 1: Trace factorial array computation

   factorial = [1, 1, 2] for n=3.

2. Step 2: Calculate indices and build result

   k=3 -> k=2 zero-based. For i=2: idx=2//2=1, pick '2'. For i=1: k=2%2=0, idx=0//1=0, pick '1'. For i=0: k=0%1=0, idx=0//1=0, pick '3'. Result = '213'.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Output matches expected k-th permutation '213' [OK]

Hint: Remember to convert k to zero-based before indexing [OK]

Common Mistakes:

• Off-by-one error in k adjustment
• Wrong index calculation in loop
• Not popping used numbers

2. Consider this modified code snippet for generating parentheses. Which line contains a subtle bug that can cause invalid sequences to be generated?

medium

A. Line with 'if close_count <= open_count:' condition

B. Line with 's.pop()' after backtrack calls

C. Line with 'if open_count < n:' condition

D. Line with 'if len(s) == 2 * n:' base case

Solution

1. Step 1: Examine close_count condition

   The condition 'close_count <= open_count' allows adding ')' even when close_count equals open_count, which can produce invalid sequences.

2. Step 2: Correct condition

   The correct condition is 'close_count < open_count' to ensure ')' is added only when there are unmatched '('.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Changing to '<' fixes invalid sequence generation [OK]

Hint: Close count must be strictly less than open count [OK]

Common Mistakes:

• Using <= instead of < for close_count condition
• Forgetting to pop after recursion

3. Examine the following code snippet for the Word Search problem. It is almost correct but contains one subtle bug. Identify the line causing the bug.

medium

A. Line where board[r][c] = temp is restored after recursion

B. Line where temp = board[r][c]

C. Line where directions are defined

D. Line missing board[r][c] = '#' to mark visited

Solution

1. Step 1: Identify missing visited marking

   The code does not mark the current cell as visited before recursive calls, allowing revisits.

2. Step 2: Understand impact of missing marking

   Without marking, dfs can revisit the same cell multiple times, causing incorrect matches or infinite loops.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Marking visited cells is essential to prevent reuse [OK]

Hint: Check if visited cells are marked before recursion [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Restoring cell too early

4. Suppose the problem changes so that each element in the input array can be used multiple times in each permutation (i.e., unlimited reuse). Which modification to the backtracking algorithm correctly generates all unique permutations with duplicates allowed and reuse permitted?

hard

A. Use backtracking without swapping, but at each recursion level, iterate over all elements and skip duplicates using a 'used' boolean array to avoid repeated elements at the same recursion depth.

B. Remove the 'seen' set and allow swapping elements freely without skipping duplicates.

C. Sort the array and use the same swapping and 'seen' set logic as before, but do not increment the recursion start index to allow reuse.

D. Generate all permutations without sorting or skipping duplicates, then filter duplicates at the end using a hash set.

Solution

1. Step 1: Understand reuse requirement

   Unlimited reuse means elements can be chosen multiple times at each recursion level, so swapping and incrementing start index is not suitable.

2. Step 2: Identify correct approach

   Backtracking without swapping, iterating over all elements at each recursion level, and using a 'used' boolean array to skip duplicates at the same depth ensures unique permutations with reuse.

3. Step 3: Evaluate other options

   Removing 'seen' causes duplicates; swapping without incrementing start index breaks logic; filtering duplicates after generation is inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Backtracking with reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Hint: Reuse requires iteration over all elements each recursion, not swapping with start index increment [OK]

Common Mistakes:

• Trying to reuse elements by swapping without adjusting recursion index or skipping duplicates properly

5. Suppose the Word Search problem is modified so that the same cell can be used multiple times in forming the word. Which modification to the backtracking algorithm correctly handles this change?

hard

A. Add a global visited set to track cells used in all paths

B. Keep marking visited cells but reset them after each recursion

C. Remove the in-place marking of visited cells to allow reuse

D. Use dynamic programming to store partial results and avoid recomputation

Solution

1. Step 1: Understand new constraint

   Cells can be reused multiple times, so marking visited cells to prevent reuse is no longer needed.

2. Step 2: Modify algorithm accordingly

   Removing in-place marking allows revisiting cells, correctly reflecting the relaxed constraint.

3. Step 3: Evaluate other options

   Keeping marking or using global visited set prevents reuse incorrectly; DP is not suitable here.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Removing visited marking enables cell reuse as required [OK]

Hint: Relaxing constraints often means removing pruning steps [OK]

Common Mistakes:

• Keeping visited marking, causing false negatives
• Adding unnecessary global state