Restore IP Addresses

Statement

Given that a string, str, contains digits, return a list of all possible valid IP addresses that can be obtained from the string.

Note: The order in which IP addresses are placed in the list is not important.

A valid IP address is made up of four numbers separated by dots ., for example, $255.255.255.123$. Each number falls between $0$ and $255$ (including $0$ and $255$), and none of them can have leading zeros.

Constraints:

• The input string str consists of digits only.

• $4 \leq$ str.length $\leq 12$

Examples