LeetCode 90. Subsets II [Medium] [C++] 解題筆記

這題算是 78. Subsets 的延伸題，一樣給定一個 array，其中數字可能重複，要我們求 array 中所有數字可以組成的不重複子集。

EX:

        Input: [1,2,2]

       Output:
        [
          [2],
          [1],
          [1,2,2],
          [2,2],
          [1,2],
          []
        ]

想法:

    基本上跟 78. Subsets 差不多，可以用類似 77. Combinations recursive 求組合數的方式求解，或是用

二進位數字表示集合的方式搭配 bitwise operation 的方式求解。但這題主要需要一點 trick 的地方是如何過濾

掉重複的子集？ 首先如果用遞迴的方式的話，直覺上可能會想到同一層遞迴深度不能重複使用同一個數字，

但是 input 的 array 同樣的數字並不一定會排在隔壁，這會造成遞歸求解時難以判斷重複數字是否已經用過，

因此在做遞迴之前我們可以先做排序，確保相同的數字會相鄰，這樣即可透過判斷當前數字與 array 中的

前一個數字是否相同來避免列舉重複的子集。另外如果利用 bitwise operation 的方法求解也必須將每個子集做排序，

確保元素相同的子集有同樣的排列順序 (ex: [4,4,1,4] and [4,1,4,4] => [1,4,4,4])，然後利用 hashmap 來過濾重複的子集。

另外bitwise operation 的方式雖然很炫炮，但是因為這題需要過濾掉重複的子集，recursive 可以透過剪枝避免掉不必要的搜索

，而 bitwise operation 的方式卻依然需要遍歷所有子集並且做多次排序，複雜度來到 O(2^n*nlogn)。

完整程式碼:

解法一( recursive with sorting)

class Solution {
public:
    vector<vector<int>> ans;
    void dfs(vector<int>& nums, int s, vector<int>& cur) {
        ans.emplace_back(cur);
        if (s == nums.size()) { return; }
        for (int i = s; i < nums.size(); i++) {
            // For the same depth, among the same numbers, only the first number can be used.
            if (i > s && nums[i] == nums[i-1]) { continue; }
            cur.emplace_back(nums[i]);
            dfs(nums, i + 1, cur);
            cur.pop_back();
        }
    }
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> cur;
        dfs(nums, 0, cur);
        return ans;
    }
};

解法二(bitwise operation with sorting):

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        const int n = nums.size();
        vector<vector<int>> ans;
        map<vector<int>, bool> stat;
        // enurmerate all states, total 2^n states
	for (int s = 0; s < 1 << n; s++) {
            vector<int> cur;
            for (int i = 0; i < n; i++) {
                if (s & (1 << i)) {
                    cur.emplace_back(nums[i]);
                }
            }
            sort(cur.begin(), cur.end());
            if (!stat[cur]) {
                ans.emplace_back(cur);
                stat[cur] = true;
            }
        }
        
        return ans;
    }
};