Dare2Solve
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]]
.
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.
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.
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.
class Solution {
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> res;
vector<int> ds;
vector<bool> flag(nums.size(), false);
unordered_set<string> keys;
sort(nums.begin(), nums.end());
backtrack(0, nums, ds, flag, keys, res);
return res;
}
private:
void backtrack(int ind, vector<int>& nums, vector<int>& ds, vector<bool>& flag, unordered_set<string>& keys, vector<vector<int>>& 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<int>& ds) {
string key;
for (int num : ds) {
key += to_string(num) + '_';
}
return key;
}
};
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
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> ds = new ArrayList<>();
boolean[] flag = new boolean[nums.length];
Set<String> 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<Integer> ds, boolean[] flag, Set<String> keys, List<List<Integer>> 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<Integer> ds) {
StringBuilder key = new StringBuilder();
for (int num : ds) {
key.append(num).append('_');
}
return key.toString();
}
}
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;
};