对于有重复数字的全排列,分析重复情况的主要来源:相同的位置选择了不同但数值相同的数字。
对于重复的数字,人为控制放入相同数字的数量(枚举从1~N),只要保证选择i
个连续相同数字后,紧跟的数字不相同(不能构成连续的i+1
个相同数字)即可保证排列唯一性。
tricks:用map存储每个数字的个数。枚举for循环结束后,统一pop出N个相同数字维护当前排列。
附上代码:
class Solution { map<int,int> vis; public: void dfs(vector<int>& nums, vector<vector<int>>& out, vector<int>& curr){ if(curr.size() >= nums.size()) { out.push_back(curr); return; } for(map<int,int>::iterator it = vis.begin(); it != vis.end(); it++){ if(curr.size() > 0 && curr.back() == it->first) continue; int temp = it->second; while(it->second > 0) { vis[it->first]--; curr.push_back(it->first); dfs(nums, out, curr); } vis[it->first] = temp; while(temp > 0){ curr.pop_back(); temp--; } } } vector<vector<int>> permuteUnique(vector<int>& nums) { vector<vector<int>> out; vector<int> current; sort(nums.begin(), nums.end()); for(auto n:nums){ if(vis.count(n) == 0) vis[n] = 1; else vis[n]++; } dfs(nums, out, current); return out; } };