47. Permutations II

Add to List

  

• Total Accepted: 106328
• Total Submissions: 338713
• Difficulty: Medium
• Contributors: Admin 

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

For example,

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

[  [1,1,2],  [1,2,1],  [2,1,1]]

 to see which companies asked this question.

【题目分析】

相比较上一个题目，这个题目中元素是可能重复的。如果还按照之前的算法，会导致很多结果是重复的。

【思路】

1. 将元素排序，这样所有重复的元素就变为相邻元素，有利于我们的处理。

2. 判断如果当前元素和它前一个元素相同，那么只有在前一个元素已经被使用情况下当前元素才能被使用，这就能避免出现重复的结果。因为无论哪种结果，重复元素在结果中的相对顺序是固定的，彼此之间没有交换位置，而这种顺序只可能有一种。

【java代码】

1 public class Solution { 2     public List
         
          
           > permuteUnique(int[] nums) { 3         Arrays.sort(nums); 4         int[] used = new int[nums.length]; 5         List
           
            
             > list = new ArrayList<>(); 6         backtrack(list, new ArrayList<>(), nums, used); 7         return list; 8     } 9     10      private void backtrack(List
             
              
               > list, List
               
                 tempList, int [] nums, int[] used){11 if(tempList.size() == nums.length){12 list.add(new ArrayList<>(tempList));13 return;14 } 15 for(int i = 0; i < nums.length; i++){ 16 if(used[i] == 1) continue;17 if(i > 0 && nums[i-1]==nums[i] && used[i-1]==0) continue;18 used[i] = 1;19 tempList.add(nums[i]);20 backtrack(list, tempList, nums, used);21 tempList.remove(tempList.size() - 1);22 used[i] = 0;23 }24 }25 }