《代码随想录》回溯算法：复原IP地址
本题的完整题目如下：
本题的完整思路如下： 1.本题使用递归以及回溯来做，所以依然分为三部曲： 2.第一步：确定递归的参数和返回值：无返回值，参数为：原数组，以及startindex。 3.第二步：确定递归的终止条件：当startindex大于等于原数组的长度时，将path数组中的每个元素之间用‘.’分隔。 4.第三步：确定单次递归函数中的逻辑：for循环中的终止条件为i<max(startindex+3,nums.length)，因为每一个最多是三位数，所以取那两个值的最大值即可。在循环时，先得到startindex到i的子字符串，然后判断其是否满足ip地址的要求，如果满足就将其添加到path数组中，并进行递归，然后是回溯。 5.其中有很多剪枝的操作，比如说当path中的元素超过4时，即可返回，因为ip地址最多就是4位。 6.回溯递归，只要三部曲写对，结果就是对的，具体原因可以用数学归纳法进行证明！ 本题的完整代码如下：
//93.复原IP地址
class Solution7 {List<String> res = new ArrayList<>();List<String> path = new ArrayList<>();public List<String> restoreIpAddresses(String s) {backtrack(s, 0);return res;}public void backtrack(String s, int startindex) {if(startindex >= s.length() && path.size() == 4) {String result = String.join(".", path);res.add(result);return;}if(path.size() >= 4){return;}for(int i = startindex; i < Math.min(startindex + 3, s.length()); i++) {String temp = s.substring(startindex, i + 1);if(isAddress(temp)) {path.add(temp);backtrack(s, i + 1);path.remove(path.size() - 1);}}}private boolean isAddress(String temp) {if(temp.charAt(0) == '0' && temp.length() > 1){return false;}int num = Integer.parseInt(temp);if(num >= 0 && num <=255){return true;}return false;}
}
《代码随想录》回溯算法：子集
本题的完整题目如下：
本题的完整思路如下： 1.本题是使用递归和回溯来求解，所以分为三步： 2.第一步：确定递归函数的参数和返回值：返回值无，参数是原数组和startindex。 3.第二步：确定递归函数的终止条件：当startindex大于等于原数组长度时，终止。但是并不是此时才收割结果，因为本题是找子集，只有一个元素也可以作为子集，所以收割结果并不在此时。 3.第三步：确定单次递归函数的逻辑：将遍历的元素添加到path集合中，将path添加到结果数组中，此处为收割结果。接着就是递归，然后是回溯。 4.本题需要注意的是，收割结果的时机，跟前几题不一样，不是达到终止条件才收割，而是每有一个元素加到path数组中，就将次数组添加到结果数组中。 本题的完整代码如下：
//78.子集
class Solution8 {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsets(int[] nums) {backtrack(nums, 0);res.add(new ArrayList<>(path));return res;}public void backtrack(int[] nums, int startindex) {if (startindex >= nums.length) {return;}for (int i = startindex; i <= nums.length - 1; i++) {path.add(nums[i]);res.add(new ArrayList<>(path));backtrack(nums, i + 1);path.remove(path.size() - 1);}}
}
《代码随想录》回溯算法：子集II
本题的完整题目如下：
本题的完整思路如下： 1.本题 与上一题相比，多一个去重步骤，因为原数组中有重复元素，如果不去重，结果中会包含一样的结果。 2.去重，首先就是对原数组进行排序，这样才能保证有效去重。 3.所以本题的大体步骤跟上一题类似，这里重点展示去重的逻辑： 4.当i>=1时，并且当前元素等于前一个元素时，并且前一个元素没有使用过，即对应的used数组对应位置为false，这样才代表后边的遍历的结果都存在与之重复的元素。而当used数组为true时，就是使用原数组中的两个相同的元素，这样不会导致重复，因为原数组就有两个相同的元素。 本题的完整代码如下：
//90.子集Ⅱ
class Solution9 {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> subsetsWithDup(int[] nums) {boolean[] used = new boolean[nums.length];res.add(new ArrayList<>(path));Arrays.sort(nums);backtrack(nums, 0, used);return res;}
public void backtrack(int[] nums, int startindex, boolean[] used) {if(startindex >= nums.length) {return;}for(int i = startindex; i < nums.length; i++) {if(i >= 1 && nums[i - 1] == nums[i] && used[i - 1] == false) {continue;}path.add(nums[i]);used[i] = true;res.add(new ArrayList<>(path));backtrack(nums, i + 1, used);path.remove(path.size() - 1);used[i] = false;}}
}