本文主要介绍三道LeetCode上的算法题目，分别是复原IP地址、子集、子集II。这三道题目均为经典的回溯算法题目，本文中将会详细介绍回溯算法的思想以及Java代码实现。
一、复原IP地址（题号：93）
1、题目描述
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
示例:
输入: “25525511135”
输出: [“255.255.11.135”, “255.255.111.35”]
2、解题思路
对于这道题目，我们可以采用回溯算法来解决。具体的思路如下：
（1）首先，我们需要定义好递归函数的参数。递归函数需要四个参数，分别表示当前已经处理的字符串的起始位置、当前已经处理的段数、当前已经处理好的IP地址以及最终结果。其中，最终结果是一个List类型的数据结构。
（2）递归函数中需要进行两个判断。第一个判断是，如果当前已经处理的段数已经等于4，那么我们就可以将当前已经处理好的IP地址添加到结果中，然后直接返回即可。第二个判断是，如果当前已经处理的字符串已经处理完了，那么我们也直接返回即可。
（3）接着，我们需要进行双重循环。第一重循环是从当前字符串的起始位置开始，到差不多结束的地方。第二重循环是从当前起始位置开始，到当前位置加上2的地方。在这个双重循环的过程中，我们需要不断地检查当前选择的字符串是否符合IP地址的要求。如果符合要求，那么我们就将这个字符串添加到当前已经处理好的IP地址中，然后递归调用自身，处理下一段，直到处理完所有的段。
3、Java代码实现
下面是Java代码的实现：
class Solution {
public List<String> restoreIpAddresses(String s) {
List<String> res = new ArrayList<>();
if (s == null || s.length() == 0 || s.length() > 12) {
return res;
}
dfs(s, 0, 0, new StringBuilder(), res);
return res;
}
private void dfs(String s, int start, int count, StringBuilder sb, List<String> res) {
if (count == 4 && start == s.length()) {
res.add(sb.toString().substring(0, sb.length() - 1));
return;
}
if (count == 4 || start == s.length()) {
return;
}
for (int i = start; i < s.length(); i++) {
if (i - start >= 3) {
return;
}
if (s.charAt(start) == '0' && i > start) {
return;
}
String sub = s.substring(start, i + 1);
if (Integer.parseInt(sub) > 255) {
return;
}
dfs(s, i + 1, count + 1, sb.append(sub).append('.'), res);
sb.delete(sb.length() - sub.length() - 1, sb.length());
}
}
}
二、子集（题号：78）
1、题目描述
给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: nums = [1,2,3]
输出:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
2、解题思路
对于这道题目，我们也可以采用回溯算法来解决。具体的思路如下：
（1）首先，我们需要定义好递归函数的参数。递归函数需要五个参数，分别表示当前已经处理的位置、当前已经处理好的子集、原始数组、当前子集的长度以及最终结果。其中，最终结果是一个List<List>类型的数据结构。
（2）在递归函数中，我们需要进行两个判断。第一个判断是，如果当前已经处理好的子集长度等于原始数组的长度，那么说明已经处理完了，我们就可以将当前子集添加到最终结果中，然后直接返回即可。第二个判断是，如果当前处理的位置已经超过了原始数组的长度，那么我们也直接返回即可。
（3）接着，我们需要进行双重循环。第一重循环是从当前位置开始，到原始数组的长度。第二重循环是从当前位置的下一个位置开始，到原始数组的长度。在这个双重循环的过程中，我们需要不断地将选择的元素添加到当前已经处理好的子集中，然后递归调用自身，处理下一个位置。
3、Java代码实现
下面是Java代码的实现：
class Solution {
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
dfs(nums, 0, new ArrayList<>(), 0, res);
return res;
}
private void dfs(int[] nums, int start, List<Integer> list, int len, List<List<Integer>> res) {
if (len == nums.length) {
res.add(new ArrayList<>(list));
return;
}
if (start >= nums.length) {
return;
}
list.add(nums[start]);
dfs(nums, start + 1, list, len + 1, res);
list.remove(list.size() - 1);
dfs(nums, start + 1, list, len, res);
}
}
三、子集II（题号：90）
1、题目描述
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
示例:
输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
2、解题思路
对于这道题目，我们同样可以采用回溯算法来解决。具体的思路如下：
（1）首先，我们需要定义好递归函数的参数。递归函数需要四个参数，分别表示当前已经处理的位置、当前已经处理好的子集、原始数组以及最终结果。其中，最终结果是一个List<List>类型的数据结构。
（2）在递归函数中，我们需要进行两个判断。第一个判断是，如果当前已经处理好的子集长度等于原始数组的长度，那么说明已经处理完了，我们就可以将当前子集添加到最终结果中，然后直接返回即可。第二个判断是，如果当前处理的位置已经超过了原始数组的长度，那么我们也直接返回即可。
（3）接着，我们需要进行双重循环。第一重循环是从当前位置开始，到原始数组的长度。第二重循环是从当前位置开始，到原始数组的长度。在这个双重循环的过程中，我们需要不断地将选择的元素添加到当前已经处理好的子集中，然后递归调用自身，处理下一个位置。需要注意的是，如果当前选择的元素和上一个选择的元素相同，那么我们就直接跳过即可。
3、Java代码实现
下面是Java代码的实现：
class Solution {
public List<List<Integer>> subsetsWithDup(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
if (nums == null || nums.length == 0) {
return res;
}
Arrays.sort(nums);
dfs(nums, 0, new ArrayList<>(), res);
return res;
}
private void dfs(int[] nums, int start, List<Integer> list, List<List<Integer>> res) {
res.add(new ArrayList<>(list));
for (int i = start; i < nums.length; i++) {
if (i > start && nums[i] == nums[i - 1]) {
continue;
}
list.add(nums[i]);
dfs(nums, i + 1, list, res);
list.remove(list.size() - 1);
}
}
}
四、总结
以上就是本文对于三道经典回溯算法题目的详细介绍。回溯算法虽然看起来比较复杂，但实际上只需要掌握好其中的递归和回溯的思想，就可以比较轻松地解决这类问题。同时，我们还需要注意一些剪枝和优化的技巧，比如在IP地址问题中，我们需要对于一些不符合IP地址要求的字符串进行剪枝，以减少递归次数。