93. 复原 IP 地址
本题和分割回文串类似，都是分割问题。每次分割出一个数字字符串，判断是否合法（没有前导零，0-255 之间），合法则加入 path。
class Solution {
private List<String> res;
private LinkedList<String> path;
public List<String> restoreIpAddresses(String s) {
res = new LinkedList<>();
if (s.isEmpty()) return res;
path = new LinkedList<>();
backtrace(s, 0);
return res;
}
public void backtrace(String s, int startIndex) {
if (path.size() == 4) {
if (startIndex >= s.length()) {
String str = String.join(".", path);
res.add(str);
}
return;
}
// i < startIndex + 3 剪枝，每次分割的字符串最多三位数
for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {
// 分割字符串
String str = s.substring(startIndex, i + 1);
// 个位数或没有前导零的多位数才是合法的数字
if (str.length() == 1 || str.charAt(0) != '0') {
// 这里使用 double，是因为有超出整数范围的用例
// 这里不用处理异常，以为题目说了 s 中只包含数字字符
double num = Double.parseDouble(str);
if (num >= 0 && num <= 255) {
path.add(str);
backtrace(s, i + 1);
path.removeLast();
}
} else {
break;
}
}
}
}时间复杂度：O(3^4 |s|)，对于字符串中的每一个数字，都有三种使用方式（数字为 0 除外，其只有一个使用方式，其余的都是前导零），分别是当前数字、当前数字和后面一位组成的二位数、当前数字和后面两位组成的三位数，然后每个数字都要求向下深入四层（字符串长度不够的除外），因为要组成 IP 地址。每个答案还都有一个拼接字符串的时间消耗，所以时间复杂度是 O(3^4 |s|)。
空间复杂度：O(4)，不计入递归，只算 path，最多放 4 个元素。
78. 子集
集合：[1, 2, 3]，子集有 [], [1], [1, 2], [1, 3], [1, 2, 3], [2], [2, 3], [3]。也是组合的一种，结集不重复，一样的思路，上 startIndex。和一般的组合不同的点在于，一般的组合的解是一个完整的 path，而子集问题的解是 path 中的任一时刻，即每次的选择都是一个解，例如：[], [1], [1, 2], [1, 2, 3]，最终 path 是 [1, 2, 3]，但是前面的过程都是解。
这道题强调了画图的重要性，尤其是 path 在各个阶段的结果。
图片来源于代码随想录，可以看到红线部分就是 path，这样直观的展示出来，也就知道了何时将解加入到结果集。
class Solution {
private List<List<Integer>> res;
private LinkedList<Integer> path;
public List<List<Integer>> subsets(int[] nums) {
res = new LinkedList<>();
path = new LinkedList<>();
backtrace(nums, 0);
return res;
}
public void backtrace(int[] nums, int startIndex) {
// 沿途都是答案
res.add(new LinkedList<>(path));
// 可以不加，因为下面的 for 也不会执行了
// if (startIndex >= nums.length) return;
for (int i = startIndex; i < nums.length; i++) {
path.add(nums[i]);
backtrace(nums, i + 1);
path.removeLast();
}
}
}90. 子集 II
因为集合中可能有重复的元素，比如有重复的 2，前面的 2 处理过了，后面的 2 就不用处理了，否则会有重复的结果，这里的一个小技巧就是将集合排序，这样相同的元素就会凑在一起，for 循环中如果发现当前元素和上一个相同，那么当前元素就不用处理了，开始下一次循环即可。
class Solution {
private List<List<Integer>> res;
private LinkedList<Integer> path;
public List<List<Integer>> subsetsWithDup(int[] nums) {
res = new LinkedList<>();
path = new LinkedList<>();
Arrays.sort(nums);
backtrace(nums, 0);
return res;
}
public void backtrace(int[] nums, int startIndex) {
res.add(new LinkedList<>(path));
for (int i = startIndex; i < nums.length; i++) {
// 和前面的元素相同，就不处理了，试探下一个
if (i > startIndex && nums[i] == nums[i - 1]) continue;
path.add(nums[i]);
backtrace(nums, i + 1);
path.removeLast();
}
}
}时间复杂度：O(n * 2^n)，共有 2^n 个子集，每个子集形成结果需要 O(n)
空间复杂度：O(n)，不计算递归的栈空间消耗，只计算 path 的大小