BM56 有重复项数字的全排列

1.题目描述

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围： 0<n≤80<n≤8 ，数组中的值满足 −1≤val≤5−1≤val≤5

要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)

示例1

输入：

[1,1,2]

返回值：

[[1,1,2],[1,2,1],[2,1,1]]

示例2

输入：

[0,1]

返回值：

[[0,1],[1,0]]

2.解题思路

相比于没有重复项数字的全排列，这一题可能会出现重复的情况

eg:

没重复时：[1,2] -> res = [1,2],[2,1]

有重复时：[1,1] -> res = [1,1],[1,1]  答案列表中会出现两次相同的path,那么就需要进行去重操作

其实进行去重也很容易实现，只需要在for循环内部，判断当前遍历的下标i处的元素，是否与它的前一个元素相同，如果相同，且前一个元素visited=0，那就说明前一个元素的path序列肯定已经被访问过，且加入到res列表中了，当前元素就可以直接跳过了，这样就排除了重复的排列

3.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型一维数组 
     * @return int整型ArrayList<ArrayList<>>
     */
    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    ArrayList<Integer> path = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        Arrays.sort(num);
        int[] visited = new int[num.length];
        backTracking(num,visited);
        return res;
    }

    public void backTracking(int[] num, int[] visited) {
        if (path.size() == num.length) {
            res.add(new ArrayList<Integer>(path));
            return;
        }
        for (int i = 0; i < num.length; i++) {
            if (visited[i] != 0 || (i > 0 && num[i] == num[i-1] && visited[i-1] == 0)) continue;
            visited[i] = 1;
            path.add(num[i]);
            backTracking(num,visited);
            path.remove(path.size()-1);
            visited[i] = 0;
        }
    }
}