I see most solutions are using next permutation. That's great and only uses O(1) space.

Anyway I am sharing backtracking solution which uses O(n) space. This is actually a typical backtracking problem. We can use hash map to check whether the element was already taken. However, we could get TLE if we check vector<int> num every time. So we iterate the hash map instead.

```
class Solution {
public:
vector<vector<int> > permuteUnique(vector<int> &num) {
vector<vector<int>> v;
vector<int> r;
map<int, int> map;
for (int i : num)
{
if (map.find(i) == map.end()) map[i] = 0;
map[i]++;
}
permuteUnique(v, r, map, num.size());
return v;
}
void permuteUnique(vector<vector<int>> &v, vector<int> &r, map<int, int> &map, int n)
{
if (n <= 0)
{
v.push_back(r);
return;
}
for (auto &p : map)
{
if (p.second <= 0) continue;
p.second--;
r.push_back(p.first);
permuteUnique(v, r, map, n - 1);
r.pop_back();
p.second++;
}
}
};
```