题解 | #没有重复项数字的全排列#
没有重复项数字的全排列
https://www.nowcoder.com/practice/4bcf3081067a4d028f95acee3ddcd2b1
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param num int整型vector
* @return int整型vector<vector<>>
*/
vector<vector<int>> ans; // 方案
vector<int> path; // 位置
vector<bool> st; // 标记是否用过
vector<vector<int> > permute(vector<int>& num) {
// write code here
sort(num.begin(),num.end()); // 排序
path = vector<int>(num.size());
st = vector<bool>(num.size());
dfs(num, 0);
return ans;
}
void dfs(vector<int>&num, int u) {
if (u == num.size()) { // u表示位置如果枚举完所有位置,说明当前就是一个方案
ans.push_back(path);
}
for (int i = 0; i < num.size(); i ++ ) {
if (!st[i]) { // 如果这个位置没有用过就填入
if (i && num[i - 1] == num[i] && !st[i - 1]) continue; // 如果前一个数等于当前数 并且 前面的位置没有被用过就跳过
path[u] = num[i]; // 填入第i数
st[i] = true; // 此时的i这个位置已经用过
dfs(num, u + 1); // 递归到下一层
st[i] = false; // 恢复现场
}
}
}
};
#没有重复项数字的全排列#