[LeetCode] Permutations II

47. Permutations II

Given a collection of numbers, nums, that might contain duplicates, return all possible unique permutations in any order.

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
class Solution {
vector<vector<int>> res;
void helper(unordered_map<int,int>& mp, int n, vector<int>& perm) {
if(!n) {
res.push_back(perm);
} else {
for(auto [k, v]: mp) {
if(!v) continue;
mp[k]--;
perm.push_back(k);
helper(mp,n-1,perm);
perm.pop_back();
mp[k]++;
}
}
}
public:
vector<vector<int>> permuteUnique(vector<int>& nums) {
unordered_map<int,int> mp;

for(auto& n : nums)
mp[n]++;

helper(mp, nums.size(), vector<int>() = {});
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/28/PS/LeetCode/permutations-ii/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.