Medium

题目描述

给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示：

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

解题思路

这道题是经典的回溯算法问题，相比于普通的全排列，这里需要处理重复元素。核心思路是通过回溯生成所有排列，但要避免重复。

解题思路：

  1. 排序预处理：首先对数组进行排序，使相同元素相邻，便于后续去重处理。

  2. 回溯框架：使用标准的回溯模板，维护一个当前排列路径和访问状态数组。

  3. 去重关键：在同一层递归中，如果当前元素与前一个元素相同且前一个元素未被使用，则跳过当前元素。这是因为在同一层选择中，相同元素的不同位置会产生重复排列。

  4. 状态管理：使用 used 数组记录每个位置的元素是否已被选择，确保每个元素在一次排列中只使用一次。

去重的核心逻辑是：if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue; 这确保了相同元素按照原数组中的顺序被选择，避免了重复排列的产生。

时间复杂度主要由排列数决定，空间复杂度为递归深度加上存储结果所需的空间。

代码实现

class Solution {
public:
    vector<vector<int>> permuteUnique(vector<int>& nums) {
        vector<vector<int>> result;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        
        sort(nums.begin(), nums.end());
        backtrack(nums, path, used, result);
        return result;
    }
    
private:
    void backtrack(vector<int>& nums, vector<int>& path, vector<bool>& used, vector<vector<int>>& result) {
        if (path.size() == nums.size()) {
            result.push_back(path);
            return;
        }
        
        for (int i = 0; i < nums.size(); i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            
            path.push_back(nums[i]);
            used[i] = true;
            backtrack(nums, path, used, result);
            path.pop_back();
            used[i] = false;
        }
    }
};

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        result = []
        path = []
        used = [False] * len(nums)
        
        nums.sort()
        self.backtrack(nums, path, used, result)
        return result
    
    def backtrack(self, nums, path, used, result):
        if len(path) == len(nums):
            result.append(path[:])
            return
        
        for i in range(len(nums)):
            if used[i]:
                continue
            if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                continue
            
            path.append(nums[i])
            used[i] = True
            self.backtrack(nums, path, used, result)
            path.pop()
            used[i] = False

public class Solution {
    public IList<IList<int>> PermuteUnique(int[] nums) {
        var result = new List<IList<int>>();
        var path = new List<int>();
        var used = new bool[nums.Length];
        
        Array.Sort(nums);
        Backtrack(nums, path, used, result);
        return result;
    }
    
    private void Backtrack(int[] nums, List<int> path, bool[] used, IList<IList<int>> result) {
        if (path.Count == nums.Length) {
            result.Add(new List<int>(path));
            return;
        }
        
        for (int i = 0; i < nums.Length; i++) {
            if (used[i]) continue;
            if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
            
            path.Add(nums[i]);
            used[i] = true;
            Backtrack(nums, path, used, result);
            path.RemoveAt(path.Count - 1);
            used[i] = false;
        }
    }
}

var permuteUnique = function(nums) {
    const result = [];
    nums.sort((a, b) => a - b);
    
    function backtrack(path, used) {
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        for (let i = 0; i < nums.length; i++) {
            if (used[i] || (i > 0 && nums[i] === nums[i-1] && !used[i-1])) {
                continue;
            }
            
            used[i] = true;
            path.push(nums[i]);
            backtrack(path, used);
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack([], new Array(nums.length).fill(false));
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n! × n)最坏情况下需要生成 n! 个排列，每个排列需要 O(n) 时间复制
空间复杂度O(n)递归栈深度为 n，used 数组和 path 数组各占 O(n) 空间

相关题目