# Accepted backtracking C++ solution by using map (28ms)

• 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++;
}
}
};``````

• It is a good way to skip the same number by using map.

• Backtracking is hard to understand. Can anyone explain why vector does not work? What is the difference?

``````void dfs(int start, vector<int>& nums, vector<int>& v, vector<vector<int>>& vv) {
if (start == nums.size()) {
vv.push_back(v);
return;
}
for (int i=start; i<nums.size(); i++) {
if (i != start && nums[i] == nums[start]) continue; // skip by position by usage??

v.push_back(nums[i]);
dfs(start+1, nums, v, vv);
v.pop_back();
}
}
vector<vector<int>> permuteUnique(vector<int>& nums) {
vector<vector<int>> vv;
vector<int> v;
dfs(0, nums, v, vv);
return vv;
}``````

• Changing the vector to set will make difference;
The vector does not work because it can not deal with the duplicate numbers;
if (i != start && nums[i] == nums[start]) continue;Can not make sure no duplicate in result;
such as 1,2,2 ,1 will exchange with 2 twice time!

• Pretty smart solution....

• I am asked to propose the solution with sorting the array first in the interview. I think this solution could be one of the answer.

• I wonder what's the time complexity of backtracking algorithm for this particular problem?

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.