代码随想录 Day28 - 回溯（四）

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());    }}

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()));    }}

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()));    }}