Time complexity for the 'Restore IP Addresses' problem
The time complexity here is exponential in s or parts, whichever is smaller.

You have a recursive function, and it calls itself three times (after removing 1, 2, or 3 characters from the beginning). Thus, if $n$ is the size of $s$ and $k$ is the number of parts, your time complexity $T(n, k)$ satisfies
$$
T(n, k) = T(n-1, k-1) + T(n-2, k-1) + T(n-3, k-1)
$$
We can roughly replace this by $T(n, k) = 3 T(n-3, k-1)$ (a lower bound) which leads to
$$
T(n, k) = \min(3^{n/3}, 3^{k}).
$$



For IP addresses, this exponential time complexity is likely not a huge problem. It's exponential in the number of parts, but the number of parts is only $4$, so that is not huge.

However, conceptually, your solution is pretty inefficient. Notice that you are duplicating a lot of work: you might call your breakString function on the tail of the same string several times, in different recursive calls.

To get a more efficient algorithm, try dynamic programming instead of recursion. For instance, can you keep track of, for each prefix and possible # of parts, whether it is a valid IP address or not? What complexity would that give?



NOTE: In the above idea to try dynamic programming, I assumed that the goal was just to return one valid IP address, not return all of them. When we have to return all of them, the time complexity changes somewhat, because the time complexity is now at least the time it takes to output all the answers, and there could be exponentially many answers.

Specifically, the time complexity in the worst case is bounded below by the number of decompositions of s in the following example: let s be a string of length $4n$ 1s, and let parts $= 2n$. Then there are at least $3^n$ decompositions: this is the number of decompositions where there is a . after every block of $4$ characters.

Here is an example: for $n = 2$, 11111111 into $4$ parts has the following $3^2 = 9$ decompositions:

1.111.1.111
1.111.11.11
1.111.111.1
11.11.1.111
11.11.11.11
11.11.111.1
111.1.1.111
111.1.11.11
111.1.111.1


Again, this includes only those decompositions with a . after every block of $4$ characters, so there are actually more than $3^n$ total. But maybe you get the idea of why it blows up exponentially.