47. Permutations II 发表于 2022-05-13 Backtracking1234567891011121314151617181920212223242526272829303132333435363738class Solution { public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> resultList = new ArrayList<>(); dfs(resultList, nums, 0); return resultList; } private void dfs(List<List<Integer>> resultList, int[] nums, int levelIndex) { // 当到达最后一个元素时,即可收集,因为最后一个元素只能与自身交换 if (levelIndex == nums.length - 1) { List<Integer> numList = new ArrayList<>(nums.length); for (int num : nums) { numList.add(num); } resultList.add(numList); return; } Set<Integer> set = new HashSet<>(); // 用于同层元素去重,如 [1, 2, 2], 其中 2 仅需被交换至索引 0 一次 // 尝试将其他位置的元素交换至 levelIndex for (int i = levelIndex; i < nums.length; i++) { // 本层已经处理过 nums[i], 此时跳过 if (!set.add(nums[i])) { continue; } swap(nums, i, levelIndex); dfs(resultList, nums, levelIndex + 1); // 进入下一层以固定下一位 swap(nums, i, levelIndex); } } private void swap(int[] nums, int i, int j) { int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }} Backtracking123456789101112131415161718192021222324252627282930313233343536class Solution { public List<List<Integer>> permuteUnique(int[] nums) { // 全排列与子集的区别在于全排列所有元素都是必须要用上的,而子集可以不选择其中一部分元素 List<List<Integer>> resultList = new ArrayList<>(); List<Integer> numList = new ArrayList<>(nums.length); boolean[] used = new boolean[nums.length]; // 需要使用 used 数组是因为可以从任意一个数字作为起点,而不是必须从最小值的数字作为起点 Arrays.sort(nums); backtrack(resultList, numList, nums, used); return resultList; } private void backtrack(List<List<Integer>> resultList, List<Integer> numList, int[] nums, boolean[] used) { if (numList.size() == nums.length) { resultList.add(new ArrayList<>(numList)); return; } for (int i = 0; i < nums.length; i++) { if (used[i]) { continue; } // 同层去重 if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) { continue; } numList.add(nums[i]); used[i] = true; backtrack(resultList, numList, nums, used); numList.remove(numList.size() - 1); used[i] = false; } }} Reference47. Permutations II剑指 Offer 38. 字符串的排列