LeetCode 筆記：Subsets II（含重複元素的子集）

一、題目描述

給定一個可能包含重複整數的集合 nums，返回所有可能的子集（冪集）。

注意：

• 子集中的元素必須按非遞減順序排列。
• 解集不能包含重複的子集。

範例：

輸入：nums = [1,2,2]

輸出：

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

二、題目分析

本題與 Subsets（不含重複元素） 類似，但輸入數組允許重複元素。關鍵在於如何避免生成重複的子集。採用深度優先搜索（DFS）回溯時，可透過排序數組，並在同一層遞歸中跳過相同的元素來實現去重。

具體做法：先對數組排序，使相同元素相鄰。在 DFS 過程中，維護一個 temp 列表記錄當前路徑。對於當前索引 index，若 index > start 且 nums[index] == nums[index-1]，則跳過該元素，避免產生重複子集。

三、示例代碼（C++）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<vector<int>> result;
        vector<int> temp;
        dfs(nums, 0, temp, result);
        return result;
    }

private:
    void dfs(const vector<int>& nums, int start, vector<int>& temp, vector<vector<int>>& result) {
        result.push_back(temp);
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i] == nums[i-1]) continue; // 跳過重複元素
            temp.push_back(nums[i]);
            dfs(nums, i + 1, temp, result);
            temp.pop_back();
        }
    }
};

四、小結

核心在於排序後配合「同層去重」策略，確保每個唯一的子集僅生成一次。時間複雜度為 O(2^n)，空間複雜度為 O(n) 遞歸棧深度。