题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
/*
当前数和前一个数相同--->只能放到当前数后面(这样可以去重)
当前数和前一个数不同--->从头开始放没有放过的地方
用一个数表示的二进制位表示某一位是否放过数:例如;9(1001),表示第0位和第3位放数了
*/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> permutation(vector<int>& nums) {
path.resize(nums.size());
sort(nums.begin(), nums.end());
dfs(nums, 0, 0, 0);
return res;
}
//u表示放了几个数,start表示可以开始放数的位置,state表示位置的状态
void dfs(vector<int> &nums, int u, int start, int state)
{
if (u == nums.size())
{
res.push_back(path);
return ;
}
if (!u || nums[u] != nums[u - 1]) start = 0;
for (int i = start; i < nums.size(); i ++)
if (!(state >> i & 1))
{
path[i] = nums[u];
dfs(nums, u + 1, i + 1, state + (1 << i));
}
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla