题目描述

输入一组数字（可能包含重复数字），输出其所有的排列方式。

样例
输入：[1,2,3]

输出：
      [
        [1,2,3],
        [1,3,2],
        [2,1,3],
        [2,3,1],
        [3,1,2],
        [3,2,1]
      ]

算法1

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

按照不含重复数字的办法去写，最后的path答案，存在一个字符串中，然后放到hash表中，判断是否重复

C++ 代码

class Solution {
public:
    int n = 0;
    vector<vector<int>> res;
    unordered_set<string > hash;

    vector<int> tmp;
    vector<bool> st;

    vector<vector<int>> permutation(vector<int>& nums) {
        n = nums.size();
        if(n < 1) return res;

        tmp = vector<int>(n,0);
        st = vector<bool>(n, false);

        dfs(nums, 0);

        return res;
    }

    void dfs(vector<int> & nums, int u){
        if(u >= n){
            string str;
            for(auto r : tmp) str += r;
            if(hash.find(str) == hash.end()){
                 res.push_back(tmp);
                 hash.insert(str);
            }
            return ;
        }

        for(int i = 0; i < n; ++i){
            if(!st[i]){
                st[i] = true;
                tmp[u] = nums[i];
                dfs(nums, u + 1);
                tmp[u] = 0;
                st[i] = false;
            }
        }

    }
};

算法2

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

C++ 代码

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    int n = 0;

    vector<vector<int>> permutation(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        n = nums.size();
        path.resize(n);

        dfs(nums, 0, 0, 0); //从第0 个数字开始枚举， 枚举每一个数字，可以放到那些位置，
                            //上一个数的位置在哪，下一个数字该从哪个位置开始放置, 
                            //0 哪个位置已经放过数字了
        return res;
    }
    void dfs(vector<int> &nums, int u, int start, int st){
        if(u == n){
            res.push_back(path);
            return;
        }

        if(!u || nums[u] != nums[u - 1]) start = 0;  //如果是第0 位数字， 或者本位数字和前以为数字不相同，
                                                    //说明 不用考虑相对位置的关系

        for(int i = start; i < n; ++i){
            if(!(st >> i & 1)){                 //第i位没有放数
                path[i] = nums[u];
                st += (1 << i); 
                dfs(nums, u + 1, i + 1, st );
                st -= (1 << i);                     //恢复现场
            }
        }

    }
};