title: Computing All Valid IP Addresses From Raw IP String
body: <p>I'm now solving leetcode problem 93. Restore IP Addresses.</p>
  <p>Here's the url link: <a href="https://leetcode.com/problems/restore-ip-addresses/" rel="nofollow noreferrer">https://leetcode.com/problems/restore-ip-addresses/</a></p>
  <p>The description looks like this:
  Given a string s containing only digits. Return all possible valid IP addresses that can be obtained from s. You can return them in any order.</p>
  <p>A valid IP address consists of exactly four integers, each integer is between 0 and 255, separated by single points and cannot have leading zeros. For example, &quot;0.1.2.201&quot; and &quot;192.168.1.1&quot; are valid IP addresses and &quot;0.011.255.245&quot;, &quot;192.168.1.312&quot; and &quot;192.168@1.1&quot; are invalid IP addresses.</p>
  <p>However, as I was trying to solve my problem via backtracking, I couldn't figure out the reason that I'm always returning an empty ArrayList. I double checked my base case and my recursion and still couldn't find the bug. Any help would be greatly appreciated, thank you!</p>
  <pre><code>public List&lt;String&gt; restoreIpAddresses(String s) {
          List&lt;String&gt; res = new ArrayList&lt;&gt;();
          if(s.length() == 0){
              return res;
          }
          int[] path = new int[4];
          snapshotIP(res,s,0,path,0);
          return res;
      }
      
      public void snapshotIP(List&lt;String&gt; res, String s, int index, int[] path, int segment){
          if(segment == 4 &amp;&amp; index == s.length()){
              res.add(path[0]+&quot;.&quot;+path[1]+&quot;.&quot;+path[2]+&quot;.&quot;+path[3]);
              return;
          }
          else if(segment == 4 || index == s.length()){
              return;
          }
          for(int len = 1; len &lt;= 3 &amp;&amp; index + len &lt;= s.length(); len++){
              String snap = s.substring(index,index+len);
              int val = Integer.parseInt(snap);
              if(val &gt; 225 || len &gt;= 2 &amp;&amp; s.charAt(index) == '0'){
                  break;
              }
              path[segment] = val;
              snapshotIP(res,s,index+len,path,segment+1);
              path[segment] = -1; //undo the choice
  
          }
      }
  </code></pre>