Medium

题目描述

给你一个整数数组 nums，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集可以按 任意顺序 排列。

示例 1：

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

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

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

解题思路

这道题是经典的回溯算法问题，关键在于处理重复元素以避免生成重复的子集。

核心思路：

  1. 排序预处理：首先对数组排序，使相同元素相邻，便于去重处理
  2. 回溯生成子集：使用深度优先搜索，每个位置有两种选择：选择当前元素或跳过
  3. 去重策略：对于重复元素，我们采用"在同一层递归中，相同元素只选择第一个"的策略

去重的具体实现：

  • 当 i > start && nums[i] == nums[i-1] 时跳过当前元素
  • 这里 start 是当前递归层的起始位置，确保我们只在同一层去重
  • 例如对于 [1,2,2]，在选择第二个位置时，如果第一个2没被选择，就不能选择第二个2

时间复杂度分析：

  • 最坏情况下需要生成 2^n 个子集
  • 每个子集的生成需要 O(n) 时间（复制到结果中）
  • 总时间复杂度为 O(n × 2^n)

这种方法比使用 Set 去重更高效，因为避免了重复子集的生成。

代码实现

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

class Solution:
    def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        result = []
        
        def backtrack(start, path):
            result.append(path[:])
            
            for i in range(start, len(nums)):
                if i > start and nums[i] == nums[i - 1]:
                    continue
                
                path.append(nums[i])
                backtrack(i + 1, path)
                path.pop()
        
        backtrack(0, [])
        return result

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

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × 2^n)需要生成最多 2^n 个子集，每个子集复制需要 O(n) 时间
空间复杂度O(n)递归栈深度最大为 n，不计算返回结果的空间

相关题目