題目敘述

題目難度: Medium
題目敘述：給定一個整數陣列 nums，回傳所有可能的子集，回傳的子集不能重複，但可以任意順序排序

這題是 78.Subsets 的延伸題型，可以看我這一篇解法，但是這題不同的是，對於 nums 陣列中 [2] 是不等於 [2,2] 的，但 [1,2] 是等於 [2,1] 的，也就是説對於個別子集來說，若相同元素但元素數量不同則看成不同子集

解法

一開始的想法

我的想法就跟上一題差不多，只是想說在添加到回傳陣列時，額外進行檢查，踢除重複的子集。

我的解法

class Solution {
public:
    vector<vector<int>> result;
    void subsetHelper(vector<int>&nums, vector<int> &cur, int depth){
        
        if(depth == nums.size()){
            for(int i=0; i< result.size(); i++){
                if(cur == result[i]) return;
            }
            result.push_back(cur);
            return;
        }
        
        //not pick
        subsetHelper(nums, cur, depth+1);

        //pick
        cur.push_back(nums[depth]);
        subsetHelper(nums, cur, depth+1);
        cur.pop_back();
    }


    vector<vector<int>> subsetsWithDup(vector<int>& nums){
        sort(nums.begin(), nums.end()); 
        vector<int> cur;
        subsetHelper(nums,cur,0);
        return result;
    }
};

這裡額外說明

1	sort(nums.begin(), nums.end());

這段的作用是對輸入陣列進行排序，這對於處理重複元素非常重要，一旦將輸入陣列排序後，所有重複的元素會相鄰排列。我們就可在遞迴處理時能夠輕鬆跳過這些重複元素。 例如，如果輸入是 [2,1,2]，排序後會變成 [1,2,2]，這樣可以在遞迴中只選擇一組 2，而不會產生重複子集

如果沒排序產生的子集可能會像是下面這樣

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

而這裡再將子集加入到回傳陣列前，進行重複檢查

執行結果

這樣做的執行結果就很爛，畢竟每次產生一種子集前都需要進行 result.size() 次的運算

更正後的解法

class Solution {
public:
    vector<vector<int>> result;
    void subsetHelper(vector<int>&nums, vector<int> &cur, int depth){
        
        result.push_back(cur);

        
        for(int i=depth; i< nums.size(); i++){
            if (i > depth && nums[i] == nums[i - 1]) continue;
            cur.push_back(nums[i]);
            subsetHelper(nums, cur, i+1);
            cur.pop_back();
        }
    }


    vector<vector<int>> subsetsWithDup(vector<int>& nums){
        sort(nums.begin(), nums.end()); 
        vector<int> cur;
        subsetHelper(nums,cur,0);
        return result;
    }
};