剑指 Offer II 084. 含有重复元素集合的全排列

这里是含有重复元素集合的全排序，核心代码是：

if (visited[i]) continue; // #1
if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) continue; // #2

#2 是去重，#1 是避免出现数据重复使用，#2 是避免出现重复的排列，比如说结果集出现 [1,1,1]、[1,1,1]，是使用 #2 来去重的。

// if (visited[i]) continue;
if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) continue;
[[1,1,1],[1,1,2],[1,2,1],[1,2,2],[2,1,1],[2,1,2],[2,2,1],[2,2,2]]
[[1,1,2],[1,2,1],[2,1,1]]


if (visited[i]) continue;
// if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) continue;
[[1,1,2],[1,2,1],[1,1,2],[1,2,1],[2,1,1],[2,1,1]]
[[1,1,2],[1,2,1],[2,1,1]]

class Solution {
    List<List<Integer>> res;
    public List<List<Integer>> permuteUnique(int[] nums) {
        if (nums == null || nums.length == 0) return new ArrayList<>(0);
        res = new ArrayList<>();
        List<Integer> path = new ArrayList<>();
        Arrays.sort(nums);
        boolean[] visited = new boolean[nums.length];
        backTracking(nums, 0, path, visited);
        return res;
    }

    private void backTracking(int[] nums, int pos, List<Integer> path, boolean[] visited) {
        if (path.size() == nums.length) {
            // collect
            res.add(new ArrayList<>(path));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i]) continue;
            if (i > 0 && nums[i - 1] == nums[i] && !visited[i - 1]) continue;
            // 允许重复
            path.add(nums[i]);
            visited[i] = true;
            backTracking(nums, i + 1, path, visited);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}