93. 复原 IP 地址
复原 IP 地址这一题感觉比较难，细节点很多，字符串遍历等均需要考虑。
package jjn.carl.backtrack; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author Jjn * @since 2023/7/29 10:49 */ public class LeetCode93 { public List<String> restoreIpAddresses(String s) { List<String> result = new ArrayList<>(); if (s.length() > 12 || s.length() < 4) { return result; } backtrack(s, result, 0, 4, new ArrayList<>()); return result; } private void backtrack(String s, List<String> result, int startIndex, int pointNum, List<String> parts) { if (startIndex == s.length()) { if (pointNum == 0) { result.add(String.join(".", parts)); return; } } for (int i = startIndex; i < startIndex + 3; i++) { if (i >= s.length()) { break; } if (s.length() - i > pointNum * 3) { continue; } if (isValidPart(s, startIndex, i)) { parts.add(s.substring(startIndex, i + 1)); backtrack(s, result, i + 1, pointNum - 1, parts); parts.remove(parts.size() - 1); } } } private boolean isValidPart(String s, int start, int end) { if (s == null || s.isEmpty()) { return false; } int subLength = end - start + 1; if (subLength > 3) { return false; } if (subLength > 1) { if (s.charAt(start) == '0') { return false; } } int sum = 0; for (int i = start; i <= end; i++) { int ithChar = s.charAt(i) - '0'; sum = 10 * sum + ithChar; } return sum >= 0 && sum <= 255; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); List<String> addresses = new LeetCode93().restoreIpAddresses(s); System.out.println(addresses.toString()); } }
78. 子集
本题目需要回溯路径上的值，故在遍历的路径上直接讲结果 add 到 result。
package jjn.carl.backtrack; import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author Jiang Jining * @since 2023-07-26 23:14 */ public class LeetCode78 { public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> result = new ArrayList<>(); backtrack(nums, 0, new ArrayList<>(), result); return result; } private void backtrack(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) { result.add(new ArrayList<>(path)); for (int i = startIndex; i < nums.length; i++) { path.add(nums[i]); backtrack(nums, i + 1, path, result); path.remove(path.size() - 1); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] nums = new int[count]; for (int i = 0; i < count; i++) { nums[i] = scanner.nextInt(); } List<List<Integer>> subsets = new LeetCode78().subsets(nums); System.out.println(String.join(",", subsets.toString())); } }
90. 子集 II
本题的难点在于，去重的逻辑，当然按照下标去重，需要先做一下排序。
package jjn.carl.backtrack; import java.util.ArrayList; import java.util.Arrays; import java.util.List; import java.util.Scanner; /** * @author Jiang Jining * @since 2023-07-26 23:32 */ public class LeetCode90 { public List<List<Integer>> subsetsWithDup(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); boolean[] used = new boolean[nums.length]; backtrack(result, nums, 0, new ArrayList<>(), used); return result; } private void backtrack(List<List<Integer>> result, int[] nums, int startIndex, List<Integer> path, boolean[] used) { result.add(new ArrayList<>(path)); for (int i = startIndex; i < nums.length; i++) { if (i >= 1 && nums[i] == nums[i - 1] && !used[i - 1]) { continue; } path.add(nums[i]); used[i] = true; backtrack(result, nums, i + 1, path, used); path.remove(path.size() - 1); used[i] = false; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int count = scanner.nextInt(); int[] nums = new int[count]; for (int i = 0; i < count; i++) { nums[i] = scanner.nextInt(); } List<List<Integer>> lists = new LeetCode90().subsetsWithDup(nums); System.out.println(String.join(",", lists.toString())); } }
