之前的回溯都是,回溯树的深度是不确定的,这次的回溯深度是确定的——4,这次的结束判定是:
- 深度为4
- 遍历到最后一个数字
private void backtracking(String[] partition, int startInde) { StringBuilder sb = new StringBuilder(""); for (int i = startIndex; i <= startIndex+3 && i < partition.length; ++i) { sb.append(partition[i]); //每个整数位于 0 到 255 之间组成 if (Integer.valueOf(sb.toString()) <= 255) { path.add(sb.toString()); //有效地址的判定条件: //1 深度为4 //2 遍历到最后一个数字 if (i == partition.length-1 && path.size() == 4) { StringBuilder ans = new StringBuilder(); //这些地址可以通过在 s 中插入 '.' 来形成 for (String s : path) { ans.append("." + s); } result.add(ans.substring(1)); } else { backtracking(partition, i+1); } path.remove(path.size()-1); } //且不能含有前导 0 if (sb.toString().equals("0")) { break; } } }