您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

LeetCode 90 Subsets II：含重複元素集合的子集生成去重

編輯：關於C++

問題描述

給定一個可能包含重複元素的整數數組 nums，返回所有不重複的子集（冪集）。子集內元素非降序，解集不能包含重複子集。

示例：nums = [1,2,2] → [[],[1],[2],[1,2],[2,2],[1,2,2]]

核心難點：去重

若直接用位掩碼枚舉 2^n 個子集，重複元素會導致相同子集被多次生成。需在生成過程中去重。

方法一：排序 + 位掩碼 + HashSet 去重（簡單但非最優）

public List> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);  // 關鍵：排序使重複元素相鄰
    Set> set = new HashSet<>();
    int n = nums.length;
    for (int mask = 0; mask < (1< subset = new ArrayList<>();
        for (int i = 0; i < n; ++i)
            if ((mask & (1<(set);
}

時間：O(n·2^n)，HashSet 操作均攤 O(1)。
空間：O(n·2^n) 存儲所有子集。
缺點：常數因子大，非面試最優解。

方法二：回溯 + 剪枝（標準最優解）

核心思想：排序後，在同一遞歸層級中，跳過與前一個元素相同且前一個元素未被選擇的元素。

public List> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List> res = new ArrayList<>();
    backtrack(nums, 0, new ArrayList<>(), res);
    return res;
}

void backtrack(int[] nums, int start, List path, List> res) {
    res.add(new ArrayList<>(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, res);
        path.remove(path.size()-1);
    }
}

剪枝條件圖解

對於 [1,2,2]，遞歸樹：


start=0: 選 1 → start=1: 選 2(索引1) → start=2: 選 2(索引2) → [1,2,2]
                              ↳ 不選 → [1,2]
                ↳ 選 2(索引2) → 被剪枝！因為 i=2 > start=1 且 nums[2]==nums[1]
        不選 1 → start=1: 選 2(索引1) → [2]
                              ↳ 選 2(索引2) → [2,2]

方法三：迭代法（基於子集增量構建）

public List> subsetsWithDup(int[] nums) {
    Arrays.sort(nums);
    List> res = new ArrayList<>();
    res.add(new ArrayList<>());
    int start = 0, end = 0;
    for (int i = 0; i < nums.length; ++i) {
        start = (i > 0 && nums[i] == nums[i-1]) ? end : 0;
        end = res.size();
        for (int j = start; j < end; ++j) {
            List cur = new ArrayList<>(res.get(j));
            cur.add(nums[i]);
            res.add(cur);
        }
    }
    return res;
}

關鍵變量：end 記錄上一輪新增子集的起始索引。若當前元素與前一個相同，只在上一輪新增的子集基礎上擴展，避免重複。