回溯中等1 种解法
#47全排列 II
为可能含重复值的数组生成所有互不重复的排列。
#回溯#数组#排序#去重
原题
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
示例 1：
输入：nums = [1,1,2] 输出： [[1,1,2], [1,2,1], [2,1,1]]
示例 2：
输入：nums = [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
提示：
1 <= nums.length <= 8-10 <= nums[i] <= 10
解题主线
- 排序后，相同值只有在前一个相同值已经用于当前路径时才允许选择，从而固定同值下标的相对顺序。
- used 解决同一下标不能重复使用，树层去重条件解决相同数值导致的重复排列。
解法 1：排序 + 使用标记去重
在普通全排列上增加同层去重：前一个相同值未被当前路径使用时，跳过当前值。
-
时间复杂度： O(n log n + n × U)，U 为不重复排列数
-
空间复杂度： O(n)，不计输出和排序副本
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
final class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
// 排序让相同值相邻，为同一树层的去重判断提供前提。
int[] numbers = nums.clone();
Arrays.sort(numbers);
List<List<Integer>> result = new ArrayList<>();
backtrack(numbers, new boolean[numbers.length], new ArrayList<>(), result);
return result;
}
private void backtrack(int[] numbers, boolean[] used,
List<Integer> path, List<List<Integer>> result) {
if (path.size() == numbers.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < numbers.length; i++) {
// used 防止同一下标在当前路径重复选择；前一同值未使用时跳过可消除同层重复。
if (used[i]) {
continue;
}
if (i > 0 && numbers[i] == numbers[i - 1] && !used[i - 1]) {
continue;
}
used[i] = true;
path.add(numbers[i]);
backtrack(numbers, used, path, result);
path.remove(path.size() - 1);
used[i] = false;
}
}
}边界与易错点
- 条件 nums[i] == nums[i - 1] && !used[i - 1] 表示树层去重；写成 used[i - 1] 是另一种较低效的剪枝语义。
- 必须先排序，否则相邻重复判断没有意义。
整理来源
由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。
backtrack/Q047_permuteII.java