剑指offer84：包含重复元素集合的全排列

剑指offer84：包含重复元素集合的全排列

题目：
给定一个可包含重复数字的整数集合 nums ，按任意顺序 返回它所有不重复的全排列。
1.输入：nums = [1,1,2]
输出：
[[1,1,2],
[1,2,1],
[2,1,1]]
2.输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
分析：
该题与83题的不同点在于如果集合中有重复的数字，那么交换集合中重复的数字得到的全排列是同一个全排列。
思路与83题基本一致，不再赘述，只说不同之处。
当处理到全排列第i个数字时，如果已经将某个值为m的数字交换为排列的第i个数字，那么遇到其他值为m的数字就跳过。
例如nums为 2，1，1，处理排列下标为0的数字时，将第一个数字1和数字2交换后，就每必要将第二个数字1和数字2交换了，将第一个数字1和数字2交换后，得到1，2，1，接着处理排列的第2个数字和第3个数字，这样就能生成两个排列1，2，1 和 1，1，2。
代码：

import java.util.HashSet;
import java.util.linkedList;
import java.util.List;
import java.util.Set;

public class PermuteUnique {
    public static void main(String[] args) {
        PermuteUnique permuteUnique = new PermuteUnique();
        int[] nums = {1,1,2};
        List> lists = permuteUnique.permuteUnique(nums);
        System.out.println(lists);
    }
        public List> permuteUnique(int[] nums) {
//        当函数helper生成的排列的下标为i的数字时，下标从0到i-1的数字都已经被选定
            List> result = new linkedList<>();
            helper(nums,0,result);
            return result;
        }

        private void helper(int[] nums, int i, List> result) {
            if (i == nums.length){
                linkedList permutation = new linkedList<>();
                for (Integer num : nums) {
                    permutation.add(num);
                }
                result.add(permutation);
            }else{
            //用来保存已经交换到排列下标为i的位置的所有值，只有当一个数值之前没有被交换到第i位才做交换否则直接跳过。
                Set set = new HashSet<>();
                for (int j = i; j < nums.length; j++) {
                    if (!set.contains(nums[j])){
                        set.add(nums[j]);
                        swap(nums,i,j);
                        helper(nums,i+1,result);
//                由于之前已经交换了数组中的两个数字，修改了排列的状态，在函数退出之前需要清除对排列状态的修改，因此交换之前交换的两个数字
                        swap(nums,i,j);
                    }

                }
            }
        }
        private void  swap(int[] nums,int i,int j){
            if (i!=j){
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
    }