AcWing 1537. 递归实现排列类型枚举 II
原题链接
简单
方法一:
class Solution {
public:
int n;
vector<vector<int>> ans;
vector<int> path;
vector<bool> st;
vector<vector<int>> permuteUnique(vector<int>& nums) {
n = nums.size();
if (!n) return {};
sort(nums.begin(), nums.end());
path = vector<int>(n);
st = vector<bool>(n);
dfs(nums, 0);
return ans;
}
void dfs(vector<int>& nums, int d)
{
if (d == n)
{
ans.push_back(path);
return;
}
for (int i = 0; i < n; i++)
{
if (!st[i])
{
if (i && nums[i] == nums[i - 1] && !st[i - 1]) continue;
st[i] = true;
path[d] = nums[i];
dfs(nums, d + 1);
st[i] = false;
}
}
}
};
方法二:
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 11;
int nums[N], path[N];
bool st[N];
int n;
void dfs(int layer)
{
if (layer == n)
{
for (int i = 0; i < n; i++) cout << path[i] << " ";
cout << endl;
return;
}
bool st2[N] = {false};
for (int i = 0; i < n; i++)
{
if (!st[i] && !st2[nums[i]])
{
st[i] = st2[nums[i]] = true;
path[layer] = nums[i];
dfs(layer + 1);
st[i] = false;
}
}
return;
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> nums[i];
sort(nums, nums + n);
dfs(0);
return 0;
}