回溯中等1 种解法

#47全排列 II

为可能含重复值的数组生成所有互不重复的排列。

#回溯#数组#排序#去重

解题主线

排序后，相同值只有在前一个相同值已经用于当前路径时才允许选择，从而固定同值下标的相对顺序。

used 解决同一下标不能重复使用，树层去重条件解决相同数值导致的重复排列。

解法 1：排序 + 使用标记去重

在普通全排列上增加同层去重：前一个相同值未被当前路径使用时，跳过当前值。

时间复杂度

O(n log n + n × U)，U 为不重复排列数

空间复杂度

O(n)，不计输出和排序副本

47. 全排列 II · 排序 + 使用标记去重

java

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++) {
            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