用回溯 + DFS 搜索全排列（去重）

题目链接-来源：力扣（LeetCode）

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]

思路：

此题沿用 上一题 的模板即可。
唯一的区别是，本题所给的数组中拥有重复元素，我们需要动用一点小技巧进行去重操作。
首先将原数组排序，方便我们后续的比较。在每轮 dfs 查找数组中的每个元素时，我们用一个局部变量 prev 记录上一次访问过的元素，后续元素必须满足与 prev 不相同的条件我们才进行考虑。prev 的初始化可以选择一个不在值域中的数字，比如本题的值域是 [-10, 10]，我取 -11。
其他代码与上一题完全一样。

时间复杂度：O(n * n!)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        // Init
        List<List<Integer>> ret = new LinkedList<>();
        int len = nums.length;
        if (len == 0) {
            return ret;
        }
        List<Integer> ans = new ArrayList<>(len);
        boolean[] visited = new boolean[len];
        Arrays.sort(nums);
        
        // Process
        dfs(nums, ret, ans, visited);
        return ret;
    }
    
    private void dfs(int[] nums, List<List<Integer>> ret, List<Integer> ans, boolean[] visited) {
        int len = nums.length;
        int size = ans.size();
        if (ans.size() == len) {
            ret.add(new ArrayList<Integer>(ans));
            return;
        }
        int prev = -11;
        for (int i = 0; i < len; i++) {
            if (!visited[i] && nums[i] != prev) {
                prev = nums[i];
                visited[i] = true;
                ans.add(nums[i]);
                dfs(nums, ret, ans, visited);
                visited[i] = false;
                ans.remove(size);
            }
        }
    }
}