1、解题思路

  1. 回溯法：使用回溯法生成所有可能的排列。在递归过程中，使用标记数组 visited 来记录哪些元素已经被使用过，避免重复使用。为了避免重复的排列，在每一层递归中跳过与前一个元素相同且未被使用的元素。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。
  2. 库函数法：使用语言内置的库函数（如 Python 的 itertools.permutations）直接生成所有排列，然后去重并排序。简单但不符合面试要求。

2、代码实现

C++
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
    vector<vector<int> > permuteUnique(vector<int>& num) {
        // write code here
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> visited(num.size(), false);
        sort(num.begin(), num.end());
        backtrack(num, path, visited, result);
        return result;
    }

    void backtrack(vector<int>& num, vector<int>& path, vector<bool>& visited,
                   vector<vector<int>>& result) {
        if (path.size() == num.size()) {
            result.push_back(path);
            return ;
        }
        for (int i = 0; i < num.size(); ++i) {
            if (visited[i] || (i > 0 && num[i] == num[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.push_back(num[i]);
            backtrack(num, path, visited, result);
            path.pop_back();
            visited[i] = false;
        }
    }
};
Java
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型一维数组
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> permuteUnique (int[] num) {
        // write code here
        ArrayList<ArrayList<Integer>> result = new ArrayList<>();
        Arrays.sort(num);
        backtrack(num, new ArrayList<>(), new boolean[num.length], result);
        return result;
    }

    private void backtrack(int[] num, ArrayList<Integer> path, boolean[] visited,
                           ArrayList<ArrayList<Integer>> result) {
        if (path.size() == num.length) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = 0; i < num.length; ++i) {
            if (visited[i] || (i > 0 && num[i] == num[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.add(num[i]);
            backtrack(num, path, visited, result);
            path.remove(path.size() - 1);
            visited[i] = false;
        }
    }
}
Python
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def permuteUnique(self , num: List[int]) -> List[List[int]]:
        # write code here
        result = []
        num.sort()
        self.backtrack(num, [], [False] * len(num), result)
        return result

    def backtrack(self, num, path, visited, result):
        if len(path) == len(num):
            result.append(path[:])
            return
        for i in range(len(num)):
            if visited[i] or (i > 0 and num[i] == num[i - 1] and not visited[i - 1]):
                continue
            visited[i] = True
            path.append(num[i])
            self.backtrack(num, path, visited, result)
            path.pop()
            visited[i] = False

3、复杂度分析

  1. 排序： 首先对数组进行排序，这样可以方便地跳过重复元素。
  2. 回溯法： 使用标记数组 visited 来记录哪些元素已经被使用过。在递归过程中，跳过与前一个元素相同且未被使用的元素，以避免重复的排列。
  3. 效率： 时间复杂度：O(n!)，因为需要生成所有可能的排列。空间复杂度：O(n!)，用于存储所有排列结果。
  4. 边界条件： 当数组长度为1时，直接返回该数组。当数组为空时，返回空列表。
  5. 适用性： 回溯法是解决排列问题的经典方法，适用于小规模数据。如果数据规模较大，应考虑其他优化方法或限制条件。