题解 | #有重复项数字的全排列#
有重复项数字的全排列
https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863
描述
给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。
数据范围： 0 < n \le 80<n≤8 ，数组中的值满足 -1 \le val \le 5−1≤val≤5
要求：空间复杂度 O(n!)O(n!)，时间复杂度 O(n!)O(n!)
示例1
输入：
[1,1,2]复制
返回值：
[[1,1,2],[1,2,1],[2,1,1]]复制
示例2
输入：
[0,1]复制
返回值：
[[0,1],[1,0]]
解题思路：
类似经典的回溯算法，此处元素值可重复，故不定根据是否重复元素来决定是否可以添加，
新增visit数组记录访问索引，确保索引不重复访问
递归前赋值，递归后复位
class Solution {
public:
vector<vector<int>> res;
vector<int> tmp;
vector<int> visit;
void dfs(vector<int> &num) {
if (tmp.size() == num.size() &&
find(res.begin(), res.end(), tmp) == res.end()) {
res.push_back(tmp);
return;
}
for (int i = 0; i < num.size(); i++) {
if (visit[i] == 0) {
tmp.push_back(num[i]);
visit[i] = 1;
dfs(num);
visit[i] = 0;
tmp.pop_back();
}
}
}
vector<vector<int> > permuteUnique(vector<int> &num) {
int n = num.size();
sort(num.begin(), num.end());
visit.resize(9, 0);
dfs(num);
return res;
}
};
