题目描述
给定一个可包含重复数字的序列,返回所有不重复的全排列。
示例1:
输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]
思路
1.这道题的思路与 46.全排列II是类似的,我们多结果进行去重处理即可。
Java代码实现
public List<List<Integer>> permuteUnique(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> cur = new ArrayList<>(); for (int i = 0; i < nums.length; i++) { cur.add(nums[i]); } backtrack(res,cur,cur.size(),0); Set<List<Integer>> set = new HashSet<>(res); return new ArrayList<>(set); } private void backtrack(List<List<Integer>> res,List<Integer> cur,int n,int first){ if(n == first){ res.add(new ArrayList<>(cur)); return ; } for(int i=first;i<n;i++){ Collections.swap(cur,i,first); backtrack(res,cur,n,first+1); Collections.swap(cur,i,first); } }
Golang代码实现
func permuteUnique(nums []int) [][]int { sort.Ints(nums) res := make([][]int,0) permuteUniqueBackTrace(nums,0,&res) return res } func permuteUniqueBackTrace(nums []int,index int,res *[][]int){ if index == len(nums){ cur := make([]int,len(nums)) copy(cur,nums) *res = append(*res,cur) return } numMap := make(map[int]int) for i := index; i<len(nums); i++{ if _,ok := numMap[nums[i]];ok{ continue } swap(nums,i,index) permuteUniqueBackTrace(nums,index+1,res) swap(nums,index,i) numMap[nums[i]] = index } } func swap(nums []int,left int,right int){ temp := nums[left] nums[left] = nums[right] nums[right] = temp }