Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example
[1,1,2] have the following unique permutations:
1
2
3
4
5
| [
[1,1,2],
[1,2,1],
[2,1,1]
]
|
Solution
% Java: 用used记录当前element是否在tmp中
(Permutations2.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> ret = new LinkedList<List<Integer>>();
if(nums==null || nums.length==0) return ret;
List<Integer> tmp = new LinkedList<Integer>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
dfs(ret,nums,used,tmp);
return ret;
}
public void dfs(List<List<Integer>> ret, int[] nums, boolean[] used, List<Integer> tmp){
if(tmp.size()==nums.length){
ret.add(new ArrayList<Integer>(tmp));
return;
}
for(int i=0;i<nums.length;i++){
if(used[i]) continue;
// used[i-1]若在tmp中，不能continue
if(i>0 && nums[i-1]==nums[i] && !used[i-1]) continue;
used[i] = true;
tmp.add(nums[i]);
dfs(ret, nums, used, tmp);
used[i] = false;
tmp.remove(tmp.size()-1);
}
}
}
|
- Python: 递归，注意去掉nums[i]==nums[i-1]的情况
(Permutations2.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution(object):
def rec(self, ret, tmp, nums):
if len(nums) == 0 and tmp not in ret:
ret.append(tmp[:])
return
for i,j in enumerate(nums):
if i > 0 and nums[i] == nums[i-1]:
continue
del nums[i]
tmp.append(j)
self.rec(ret,tmp,nums)
nums.insert(i,j)
tmp.pop()
return
def permuteUnique(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
ret =[]
if len(nums) == 0:
return ret
self.rec(ret,[],sorted(nums))
return ret
if __name__ == "__main__":
sol = Solution()
sol.permuteUnique([1,1,2]
|