
Description
The problem is to generate all unique permutations of a list of integers, where the list may contain duplicate elements. For example, given the list [1, 1, 2]
, the unique permutations are [[1, 1, 2], [1, 2, 1], [2, 1, 1]]
.
Intuition
When dealing with permutations where duplicates are present, a straightforward approach can generate duplicate permutations. To handle this, we need to ensure that each permutation is unique. A common technique is to use a backtracking approach combined with a set to track the permutations we've already encountered. By generating permutations recursively and using a set to check for uniqueness, we can avoid adding duplicates to our result.
Approach
- Sorting: First, sort the input list to facilitate easy skipping of duplicates.
- Backtracking: Use a recursive function to generate permutations. Keep track of the current permutation and a flag array to mark which elements are used.
- Uniqueness: Use a set to track and avoid adding duplicate permutations. Convert each permutation to a string key to ensure that each permutation is unique.
- Base Case: If the current permutation has the same length as the input list, add it to the result list if it hasn't been added before.
- Recursive Case: Iterate through the list, skipping over duplicates using the sorted property and the flag array.
Complexity
Time Complexity:
The time complexity is (O(N!)), where (N) is the number of elements in the list. This is because there are (N!) possible permutations, and each permutation is generated and checked.
Space Complexity:
The space complexity is (O(N \cdot N!)). The space is used for storing all unique permutations (which can be (N!) permutations, each of length (N)) and the recursion stack, which can go up to (O(N)) depth.
Code
C++
class Solution {
public:
vector> permuteUnique(vector& nums) {
vector> res;
vector ds;
vector flag(nums.size(), false);
unordered_set keys;
sort(nums.begin(), nums.end());
backtrack(0, nums, ds, flag, keys, res);
return res;
}
private:
void backtrack(int ind, vector& nums, vector& ds, vector& flag, unordered_set& keys, vector>& res) {
if (ds.size() == nums.size()) {
string key = createKey(ds);
if (keys.find(key) == keys.end()) {
keys.insert(key);
res.push_back(ds);
}
return;
}
for (int i = 0; i < nums.size(); i++) {
if (!flag[i]) {
ds.push_back(nums[i]);
flag[i] = true;
backtrack(i + 1, nums, ds, flag, keys, res);
ds.pop_back();
flag[i] = false;
}
}
}
string createKey(vector& ds) {
string key;
for (int num : ds) {
key += to_string(num) + '_';
}
return key;
}
};
Python
class Solution:
def permuteUnique(self, nums):
res = []
keys = set()
def backtrack(ind, ds, flag):
if len(ds) == len(nums):
key = '_'.join(map(str, ds))
if key not in keys:
keys.add(key)
res.append(ds[:])
return
for i in range(len(nums)):
if not flag[i]:
ds.append(nums[i])
flag[i] = True
backtrack(i + 1, ds, flag)
ds.pop()
flag[i] = False
backtrack(0, [], [False] * len(nums))
return res
Java
class Solution {
public List> permuteUnique(int[] nums) {
List> res = new ArrayList<>();
List ds = new ArrayList<>();
boolean[] flag = new boolean[nums.length];
Set keys = new HashSet<>();
java.util.Arrays.sort(nums);
backtrack(0, nums, ds, flag, keys, res);
return res;
}
private void backtrack(int ind, int[] nums, List ds, boolean[] flag, Set keys, List> res) {
if (ds.size() == nums.length) {
String key = createKey(ds);
if (!keys.contains(key)) {
keys.add(key);
res.add(new ArrayList<>(ds));
}
return;
}
for (int i = 0; i < nums.length; i++) {
if (!flag[i]) {
ds.add(nums[i]);
flag[i] = true;
backtrack(i + 1, nums, ds, flag, keys, res);
ds.remove(ds.size() - 1);
flag[i] = false;
}
}
}
private String createKey(List ds) {
StringBuilder key = new StringBuilder();
for (int num : ds) {
key.append(num).append('_');
}
return key.toString();
}
}
JavaScript
var permuteUnique = function (nums) {
const res = [];
const keys = [];
function f(ind, ds, flag) {
if (ds.length == nums.length) {
const key = ds.join('_');
if (keys.indexOf(key) == -1) {
keys.push(key);
res.push([...ds]);
}
return;
}
for (let i = 0; i < nums.length; i++) {
if (!flag[i]) {
ds.push(nums[i]);
flag[i] = 1;
f(i + 1, ds, flag);
ds.pop();
flag[i] = 0;
}
}
}
f(0, [], {});
return res;
};