题目描述

含重复元素的排列

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

先排序，按位置枚举，记录有没有用过该位置以及新的元素该从哪个位置开始枚举。
规定重复的只能在第一次出现的后面，防止重复

时间复杂度

参考文献

C++ 代码

class Solution {
public:

    vector<vector<int>> ans;
    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 ans;
    }

    void dfs(vector<int> &nums, int u, int start, int state) //u:当前枚举的位置  start：当前应该从哪个位置开始枚举 state：哪些位置用过
    {
        if (u == nums.size())
        {
            ans.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)) //第i个位置有没有用过
            {
                path[i] = nums[u];
                dfs(nums, u + 1, i + 1, state + (1 << i));//把state的第i位从0变为1
            }
    }
};