> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/backtracking/93-restore-ip-addresses.md).

# 93 Restore IP Addresses

## 93. [Restore IP Addresses](https://leetcode.com/problems/restore-ip-addresses/description/)

## 1. Question

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:\
Given`"25525511135"`,

return`["255.255.11.135", "255.255.111.35"]`. (Order does not matter)

## 2. Implementation

**(1) Backtracking**

```java
class Solution {
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<>();

        if (s == null || s.length() == 0) {
            return res;
        }

        List<String> parts = new ArrayList<>();
        getIpAddresses(s, 0, parts, res);
        return res;
    }

    public void getIpAddresses(String s, int start, List<String> parts, List<String> res) {
        if (start == s.length() && parts.size() == 4) {
            res.add(parts.get(0) + "." + parts.get(1) + "." + parts.get(2) + "." + parts.get(3));
            return;
        }

        // ip地址由4部分组成，每个部分有1-3个数位组成，4 - parts.size()表示我们需要的ip地址剩余的部分，s.length() - start表示目前string剩下的长度
        // 以下两种情况我们会停止搜索
        // 1. 如果ip地址每个部分由1个数位组成，那么我们需要的ip地址剩余的部分至少为4 - parts.size(), 如果4 - parts.size()大于string剩下的长度，说明string剩余的长度无法构成由1个数位组成4个部分的ip地址
        // 2. 如果ip地址每个部分由3个数位组成，那么我们需要的ip地址剩余部分最多为3 * (4 - parts.size()), 如果3 * (4 - parts.size())小于剩余string剩下的长度，说明string无法完全用来构成ip地址
        if (4 - parts.size() > s.length() - start || 4 - parts.size() < (s.length() - start) / 3) {
            return;
        }

        for (int i = start; i < start + 3 && i < s.length(); i++) {
            String part = s.substring(start, i + 1);

            if (isValid(part)) {
                parts.add(part);
                getIpAddresses(s, i + 1, parts, res);
                parts.remove(parts.size() - 1);
            }
        }
    }

    public boolean isValid(String s) {
        if (s.startsWith("0") && s.length() > 1) {
            return false;
        }
        int num = Integer.parseInt(s);
        return num >= 0 && num <= 255;
    }
}
```

## 3. Time & Space Complexity

**Backtracking：** 时间复杂度O() ?, 空间复杂度O() ?