题解 | #有重复项数字的全排列#
有重复项数字的全排列
https://www.nowcoder.com/practice/a43a2b986ef34843ac4fdd9159b69863
class Solution {
public:
vector<vector<int>> ans; // 方案
vector<int> path; // 位置
vector<bool> st; // 标记是否用过
vector<vector<int>> permuteUnique(vector<int>& nums) {
sort(nums.begin(),nums.end()); // 排序
path = vector<int>(nums.size());
st = vector<bool>(nums.size());
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums, int u) {
// sort(nums.begin(),nums.end()); // 排序
if (u == nums.size()) { // 如果到了最后一层结点的说明我们找到了答案就加入
ans.push_back(path);
return;
}
for (int i = 0; i < nums.size(); i ++ ) {
if (st[i] == false) { // 如果这个位置没有用过就填入
if (i && nums[i - 1] == nums[i] && !st[i - 1]) continue; // 如果前一个数等于当前数 并且 前面的位置没有被用过就跳过
path[u] = nums[i]; // 填入第i数
st[i] = true; // 此时的i这个位置已经用过
dfs(nums, u + 1); // 递归到下一层
st[i] = false; // 恢复现场
}
}
}
};
凡岛公司福利 505人发布
