分析

• 本题的考点：递归回溯。

• 这个题目使用暴搜搜出所有的方案即可，关键问题是搜索顺序是什么？一般由两种搜索顺序：

（1）可以枚举每个位置放置哪个数据；（最常用）

（2）枚举每个数据放置到哪个位置上。

• 这里使用第（1）中枚举方式。

• 这里使用数据st表示某个某个数据是否已经被使用。

• 这一题和Leetcode 0046 全排列唯一的区别是存在重复元素，因此我们要考虑如何不枚举重复方案。

• 关键对于相同元素的处理，只要我们在枚举的过程中保证相同元素枚举的顺序相同，就不会出现重复方案，例如存在数组中存在三个1，记为$1^1, 1^2, 1^3$，对于两种不同的方案，我们只要保证这三个1出现的相对顺序一样即可，例如$1^1$必须在$1^2$之前，$1^2$必须在$1^3$之前，下面就采用这种相对顺序。

• 为了方面判断是否存在重复元素，在递归搜索前将数组排序，这样相同的元素一定会排在一起，当枚举到某个位置的第i个元素时，只要i>0 && nums[i]== nums[i-1] && !st[i-1]，则此时我们就不应该使用第i个元素，直接跳过这种情况就即可。

代码

• C++

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;  // 每次搜到的方案
    vector<bool> st;  // st[i] == true说明nums[i]已经被使用了

    vector<vector<int>> permuteUnique(vector<int>& nums) {

        sort(nums.begin(), nums.end());
        path = vector<int>(nums.size());
        st = vector<bool>(nums.size());
        dfs(nums, 0);
        return ans;
    }

    void dfs(vector<int> &nums, int u) {
        if (u == nums.size()) {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); i++)
            if (!st[i]) {
                if (i && nums[i] == nums[i - 1] && !st[i - 1]) continue;  // 防止搜到重复方案(前提：排序)
                path[u] = nums[i];
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
            }
    }
};

• Java

class Solution {

    List<List<Integer>> ans = new ArrayList<>();
    LinkedList<Integer> path = new LinkedList<>();
    boolean[] st;

    public List<List<Integer>> permuteUnique(int[] nums) {

        Arrays.sort(nums);
        st = new boolean[nums.length];
        dfs(nums, 0);
        return ans;
    }

    private void dfs(int[] nums, int u) {
        if (u == nums.length) {
            ans.add((List<Integer>)path.clone());
            return;
        }

        for (int i = 0; i < nums.length; i++)
            if (!st[i]) {
                if (i > 0 && nums[i] == nums[i - 1] && !st[i - 1]) continue;
                path.add(nums[i]);
                st[i] = true;
                dfs(nums, u + 1);
                st[i] = false;
                path.removeLast();
            }
    }
}

时空复杂度分析

• 时间复杂度：$O(n!)$，n为输入数组的长度。

• 空间复杂度：$O(n)$，n为输入数组的长度。这里不考虑存储答案的二维数组，考虑的话空间复杂度为$O(n \times n!)$。