2020年9月18日 全排列 II permuteUnique

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {

    }
}

解题思路：

这道题我的思路是选择递归算法，我们求[1,1,2]组成的所有组合，可以把它降级成为求以1开头，[1,2]组成的所有组合。

然后我们循环完这个数组，把递归得到的结果也就是[1,2]能够组成的所有组合前面再加上当前正在循环的数字。就得到了以1开头的所有组合。

需要注意的是，由于存在重复的数字，所以我们需要先对循环的数做一个去重的操作。

代码实现：

这道题和前面几天的题目特别像，所以实现起来也挺简单的。

    public List<List<Integer>> permuteUnique(int[] nums) {
        
        int len=nums.length;
        List<List<Integer>> res=new ArrayList<>();
        if (len==0)
            return res;
        if (len==1)
        {
            List<Integer> list=new ArrayList<>();
            list.add(nums[0]);
            res.add(list);
            return res;
        }

        //数字去重
        HashSet<Integer> hashSet=new HashSet<>();
        
        for (int i=0;i<len;i++){
            //重复数字不处理
            if (!hashSet.contains(nums[i])){
                hashSet.add(nums[i]);
                int[] newNums=new int[len-1];
                
                //新建一个数组开始递归
                System.arraycopy(nums,0 ,newNums ,0 ,i );
                System.arraycopy(nums,i+1 ,newNums ,i ,len-i-1 );
                
                //在递归的元素前面加上这个数字
                List<List<Integer>> lists = permuteUnique(newNums);

                for (List<Integer> list : lists) {
                    list.add(0,nums[i] );
                }
                res.addAll(lists );
            }
        }
        return res;
    }