题目描述

本题最先我只想到了有多少方案数，但是对于求解出左右的方案数，还没有思路，看了yac大佬的视频后有感，以下是我对该解法的一些认识。第一我们需要知道为什么需要规定相同元素必须在前一个元素后面进行插入的原因，很简单，是为了消除相同元素之间的排列，相同元素之间的排列是无意义的。第二点很重要的是弄明白dfs函数的参数意义，第一个参数vector[HTML_REMOVED]& nums是排好序的，无论升序还是降序均可，排序的意义只是为了将相同元素聚集在一起，第二个参数u表示的是已经枚举了多少个元素，第三个元素表示的是假如下一个元素和当前元素相同时，下一个元素的枚举起点，最后一个state很简单，表示的是哪些位置被枚举过了，如果说nums的size太大了，可以尝试利用数组来实现，因为int类型的可以表示的数目为31位，为什么是31位呢，因为当1<<31的时候，其第一位是1，表示的是负数，当利用state>>i&1就会出现错误，此处尚未进行证明，有大佬可以证明下 哈哈

算法1

(暴力枚举)

时间复杂度分析：可以理解为所有数字的全排列，再除以全排列中的重复数字之间的排列即可，时间复杂度还是挺高的

C++ 代码

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;
    }
    //@param  nums   排好序的数组
    //@param  u      枚举到第几位数字
    //@param  start  下一位数字开始枚举的位置
    //@param  state   n位二进制数表示哪些位置已经被用完了，如果此题的范围较大的时候，可以使用数组来代替
    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));
            }
    } 
};