47.全排列2

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

示例 1：

1
2
3
4
5
输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

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

Solution

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
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
   
    // 用于存储当前路径的列表
    private List<Integer> path=new ArrayList<>();
    // 用于标记数字是否在当前路径中
    private boolean[] onPath;
    // 用于存储所有可能的排列结果的列表
    private final List<List<Integer>> ans = new ArrayList<>();

    // 主要方法，生成输入数组的所有排列组合
    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        // 初始化标记数组，其长度为输入数组的长度
        onPath = new boolean[nums.length];
        // 开始深度优先搜索，初始状态为索引 0
        dfs(0,nums);
        return ans;
    }

    // 深度优先搜索方法
    private void dfs(int i,int [] nums) {
        // 如果路径长度等于输入数组的长度，说明找到了一个合法的排列
        if (i == nums.length) {
            // 将当前路径添加到结果列表中
            ans.add(new ArrayList<>(path));
            return;
        }

        // 遍历所有可能的数字
        for (int j = 0; j < nums.length; ++j) {
            // 如果数字不在当前路径中
            if (!onPath[j]) {
                // 将当前数字添加到路径中
                path.add(nums[j]);
                // 标记当前数字在路径中
                onPath[j] = true;
                // 继续搜索下一个位置
                dfs(i + 1,nums);
                // 回溯，移除当前数字标记和元素
                path.remove(path.size()-1);
                onPath[j] = false;
            }
           while (j < nums.length - 1 && nums[j] == nums[j + 1]&&onPath[j]==false) {
                ++j;
            }
        }
    }
}