LC 47 Permutations II(M)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

For example, [1,1,2] have the following unique permutations:

边界条件

解题思路

这道题是之前那道 Permutations 全排列的延伸，由于输入数组有可能出现重复数字，如果按照之前的算法运算，会有重复排列产生，我们要避免重复的产生，在递归函数中要判断前面一个数和当前的数是否相等，如果相等，前面的数必须已经使用了，即对应的visited中的值为1，当前的数字才能使用，否则需要跳过，这样就不会产生重复排列了，

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> res = new ArrayList<>();
    if(nums==null || nums.length<1){
        return res;
    }
    // 排序保证可以前后比较重复的元素
    Arrays.sort(nums);
    boolean[] visited = new boolean[nums.length];
    List<Integer> perm = new ArrayList<Integer>();
    helper(res, nums, perm, visited);
    return res;
}
public void helper(List<List<Integer>> res, int[] nums, List<Integer> perm, boolean[] visited){
    if(perm.size() == nums.length){
        res.add(new ArrayList<>(perm));
    }else{
        for(int i = 0; i < nums.length; i++){
            if(visited[i])
                continue;
            //判断当前值是和前一值重复，并且前一值已经使用过
            if(i>0 && (nums[i] == nums[i-1]) && visited[i-1])
                continue;
            perm.add(nums[i]);
            visited[i] = true;
            helper(res, nums, perm, visited);
            perm.remove(perm.size() -1);
            visited[i] = false;
        }
    }
}