题目描述

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

样例

输入：[1,2,3]

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

算法

(递归，DFS)

1. 详细说一下dfs()函数，参数分别是(A, u, start, state)。其中，u表示枚举到了第几个坑。start存储的是当前这个数应该从哪一位开始枚举（也就是上一个数的后面一位）。因为遇见相同的数时，要在相同的数的后面去放。state表示的是 二进制数的状态。
2. dfs()函数中，如果u枚举到了最后一位，说明方案合法，直接存储res中
3. 如果当前u为0，表示是第一位，或者，前后2个数不相等，那么start可以为0，也就是 没有相对顺序的约束存在。
4. 如果A[u]和A[u - 1]相同，就必须遵守 相对顺序。从start开始枚举，如果第i位没有放过数字，就放数字A[u]，然后放完数字A[u]后，dfs到下一层，对应的start和state都要变。
5. 说几个关键点——

   • dfs()中的for()循环中的递归dfs(u + 1,i + 1)的意思是，第i位已经放了A[u]了，接下来看第i+1位是否可以放A[u + 1]这个数。
   • 然而for()循环中的判断条件中的i ++表示，第i位或第i+1位是否能放A[u]。
   • for()循环结束的时候，就意味着start从第0位到第n-1位，均已经尝试过，也就是A数组的第一个数放在第1个坑，第2个坑，…，直到第n-1个坑的所有可能方案。如果合法，已经放进ans中，不合法，则没有care。

6. 这道题没有回溯，或者说恢复现场？应该是个内部的dfs()。
7. 一开始要对A数组进行排序，不过忘记sort了也AC了。

时间复杂度

$O(n × n!)$
搜索树中最后一层共$n!$个节点，前面所有层加一块的节点数量相比于最后一层节点数是无穷小量，可以忽略。且最后一层节点记录方案的计算量是$O(n)$，所以时度是$O(n×n!)$。

C++ 代码

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

    void dfs(vector<int> &A, int u, int start, int state)
    {
        if(u == A.size())
        {
            res.push_back(path);
            return;
        }

        if(!u || A[u] != A[u - 1]) start = 0;
        for(int i = start; i < A.size(); i ++)
        {
            if(!(state >> i & 1))
            {
                path[i] = A[u];
                dfs(A, u + 1, i + 1, state + (1 << i));
            }
        }
    }

    vector<vector<int>> permutation(vector<int>& A) {
        path.resize(A.size());
        dfs(A, 0, 0, 0);
        return res;
    }
};

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

    void dfs(vector<int> &A, int u, int start, int state)
    {
        if(u == A.size())
        {
            res.push_back(path);
            return;
        }

        if(!u || A[u] != A[u - 1]) start = 0;
        for(int i = start; i < A.size(); i ++)     // **2
        {
            if(!(state >> i & 1))
            {
                path[i] = A[u];
                dfs(A, u + 1, i + 1, state + (1 << i));  // **1
            }
        }
    }

    vector<vector<int>> permutation(vector<int>& A) {
        path.resize(A.size());
        sort(A.begin(), A.end());
        dfs(A, 0, 0, 0);
        return res;
    }
};