代码随想录 Day29 - 回溯（五）

package jjn.carl.backtrack;
import java.util.*;
/** * @author Jjn * @since 2023/7/29 13:26 */public class LeetCode491 {    public List<List<Integer>> findSubsequences(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        backtrack(nums, result, 0, new ArrayList<>());        return result;    }            private void backtrack(int[] nums, List<List<Integer>> result, int startIndex, List<Integer> path) {        if (path.size() >= 2) {            result.add(new ArrayList<>(path));        }        Set<Integer> set = new HashSet<>();        for (int i = startIndex; i < nums.length; i++) {            if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) || set.contains(nums[i])) {                continue;            }            path.add(nums[i]);            set.add(nums[i]);            backtrack(nums, result, i + 1, path);            path.remove(path.size() - 1);        }    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int totalNumber = scanner.nextInt();        int[] nums = new int[totalNumber];        for (int i = 0; i < totalNumber; i++) {            nums[i] = scanner.nextInt();        }        List<List<Integer>> subsequences = new LeetCode491().findSubsequences(nums);        System.out.println(String.join(",", subsequences.toString()));    }}

package jjn.carl.backtrack;
import ljl.alg.wangzheng_camp.round1.tree._offer34_path_sum;
import java.util.ArrayList;import java.util.List;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 14:02 */public class LeetCode46 {    public List<List<Integer>> permute(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        boolean[] used = new boolean[nums.length];        backtrack(nums, 0, new ArrayList<>(), result, used);        return result;    }        private void backtrack(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result, boolean[] used) {        if (startIndex == nums.length) {            result.add(new ArrayList<>(path));            return;        }        for (int i = 0; i < nums.length; i++) {            if (used[i]) {                continue;            }            path.add(nums[i]);            used[i] = true;            backtrack(nums, startIndex + 1, path, result, used);            path.remove(path.size() - 1);            used[i] = false;        }    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] nums = new int[total];        for (int i = 0; i < total; i++) {            nums[i] = scanner.nextInt();        }        List<List<Integer>> list = new LeetCode46().permute(nums);        System.out.println(String.join(",", list.toString()));    }}

package jjn.carl.backtrack;
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/29 14:11 */public class LeetCode47 {    public List<List<Integer>> permuteUnique(int[] nums) {        List<List<Integer>> result = new ArrayList<>();        Arrays.sort(nums);        boolean[] used = new boolean[nums.length];        backtrack(nums, new ArrayList<>(), result, used);        return result;    }        private void backtrack(int[] nums, List<Integer> path, List<List<Integer>> result, boolean[] used) {        if (path.size() == nums.length) {            result.add(new ArrayList<>(path));            return;        }        for (int i = 0; i < nums.length; i++) {            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {                continue;            }            if (!used[i]) {                path.add(nums[i]);                used[i] = true;                backtrack(nums, path, result, used);                used[i] = false;                path.remove(path.size() - 1);            }        }    }        public static void main(String[] args) {        Scanner scanner = new Scanner(System.in);        int total = scanner.nextInt();        int[] nums = new int[total];        for (int i = 0; i < total; i++) {            nums[i] = scanner.nextInt();        }        List<List<Integer>> lists = new LeetCode47().permuteUnique(nums);        System.out.println(String.join(",", lists.toString()));    }}