LeetCode 90. 子集 II：處理重複元素的子集生成算法詳解

題目描述

給定一個可能包含重複元素的整數集合 S，要求返回所有可能的子集（冪集）。解集不能包含重複的子集，且每個子集內的元素必須按非遞減順序排列。

範例： 若 S = [1,2,2]，一個解為：

 [
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

核心思路

此題與 LeetCode 78. 子集 唯一的區別在於輸入數組包含重複元素。解決重複子集問題的關鍵在於排序 + 剪枝：

1. 先對數組進行排序，使相同元素相鄰。
2. 在深度優先搜索（DFS）遞歸過程中，若當前元素與前一個元素相同，且前一個元素在同一層遞歸中未被選擇（即 `i != index`），則跳過當前元素，避免生成重複子集。

算法實現 (C++)

class Solution {
public:
    vector> subsetsWithDup(vector& S) {
        sort(S.begin(), S.end()); // 關鍵步驟：排序
        vector> result;
        vector path;
        result.push_back(path); // 空集
        for (int k = 1; k <= S.size(); ++k) {
            dfs(S, k, 0, path, result);
        }
        return result;
    }

private:
    void dfs(const vector& S, int k, int start, vector& path, vector>& result) {
        if (path.size() == k) {
            result.push_back(path);
            return;
        }
        for (int i = start; i < S.size(); ++i) {
            // 去重核心邏輯：同層遞歸中跳過相同元素
            if (i != start && S[i] == S[i-1]) continue;
            path.push_back(S[i]);
            dfs(S, k, i + 1, path, result);
            path.pop_back();
        }
    }
};

複雜度分析

• 時間複雜度： O(N * 2^N)，其中 N 為數組長度。生成所有子集需 2^N，複製子集需 O(N)。
• 空間複雜度： O(N) 遞歸棧深度 + O(N * 2^N) 存儲結果。

關鍵點總結

去重條件 `if (i != start && S[i] == S[i-1])` 是精髓所在。`i != start` 確保我們只在「同一層遞歸的橫向遍歷」中跳過重複元素，而允許在「縱向遞歸深入」時選擇相同元素（如選取兩個 2 組成 [2,2]）。