LeetCode 47. Permutations II

47. Permutations II

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]
]

Subscribe to see which companies asked this question.

【题目分析】

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

【思路】

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

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

【java代码】

 1 public class Solution {
 2     public List<List<Integer>> permuteUnique(int[] nums) {
 3         Arrays.sort(nums);
 4         int[] used = new int[nums.length];
 5         List<List<Integer>> list = new ArrayList<>();
 6         backtrack(list, new ArrayList<>(), nums, used);
 7         return list;
 8     }
 9     
10      private void backtrack(List<List<Integer>> list, List<Integer> 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 }