给定一个可包含重复数字的序列 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]]
提示:
1 <= nums.length <= 8
-10 <= nums[i] <= 10
leetcode 第47题 解题思路
这也是一个递归问题。解题思路与46图题基本一致,但是却必须做出一些,改变,首先必须使得数组有序,在对数组中的每个元素进行全排列的时候,如果该元素与前一个元素相同,且前面一个元素已经完成了全排列,则跳过这个元素。
class Solution { List<List<Integer>> res = new ArrayList<>(); boolean[] used = null; public List<List<Integer>> permuteUnique(int[] nums) { res.clear(); if(nums.length==0) return res; used = new boolean[nums.length]; Arrays.sort(nums); permuteAux(nums,0, new ArrayList<>()); return res; } private void permuteAux(int[] nums,int index,List<Integer> st) { if(index == nums.length){ List<Integer> t = new ArrayList<>(st); res.add(t); return; } for(int i=0;i<nums.length;i++){ if(used[i]) continue; if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue; st.add(nums[i]); used[i] = true; permuteAux(nums,index+1,st); used[i] = false; st.remove(st.size()-1); } return; } }