47 Permutations II

1. Question

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
[
2
[1,1,2],
3
[1,2,1],
4
[2,1,1]
5
]
Copied!

2. Implementation

(2) Backtracking
1
class Solution {
2
public List<List<Integer>> permuteUnique(int[] nums) {
3
List<List<Integer>> res = new ArrayList<>();
4
List<Integer> permutation = new ArrayList<>();
5
boolean[] used = new boolean[nums.length];
6
Arrays.sort(nums);
7
getPermutation(nums, used, permutation, res);
8
return res;
9
}
10
11
public void getPermutation(int[] nums, boolean[] used, List<Integer> permutation, List<List<Integer>> res) {
12
if (permutation.size() == nums.length) {
13
res.add(new ArrayList<>(permutation));
14
return;
15
}
16
17
for (int i = 0; i < nums.length; i++) {
18
if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
19
continue;
20
}
21
22
if (!used[i]) {
23
used[i] = true;
24
permutation.add(nums[i]);
25
getPermutation(nums, used, permutation, res);
26
permutation.remove(permutation.size() - 1);
27
used[i] = false;
28
}
29
}
30
}
31
}
Copied!

3. Time & Space Complexity

Backtracking: 时间复杂度O(n!), 空间复杂度O(n!)