90. 子集 II

前置題目：78. 子集\

思路

題目會有重複元素，組合當中不能有重複的部分。
舉例來說：如果當前數組是[2,1,2,1,2,1,1]，如果依舊用選或不選的方法的話，
會有多種[2,1]被包含進去，而這不是我們想要的。

為了解決重複計算的問題，首先對數組排序，變成[1,1,1,1,2,2,2]，

• 此時數字1的部分有五種選擇：選定 0, 1, 2, 3, 4 個 1。
• 數字2的部分有四種選擇：選定 0, 1, 2, 3 個 2。

將這些選擇組合起來，就不會有重複的部分，像是剛才重複選擇「一個1，一個2」的情況。

程式碼

class Solution {
public:
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> res;
        vector<int> curPath(n);
        ranges::sort(nums);
        // i: 當前選擇到的位置
        // size: 目前選擇的數字有多少
        auto dfs = [&](this auto&&dfs, int i, int size) -> void {
            if(i == n) { // 沒有數字可選，遞迴結束
                res.push_back(vector<int>(curPath.begin(), curPath.begin() + size));
            }
            else { 
                int j = i + 1; // j 最後停在不等於 nums[i] 的位置上
                while(j < n && nums[i] == nums[j]) {
                    ++j;
                }
                dfs(j, size); // 不選
                while(i < j) { // 可以選擇多個相同數字，直到 nums[j] (nums[i] != nums[j])
                    curPath[size++] = nums[i++];
                    dfs(j, size); // 選
                }
            }
        };
        dfs(0, 0);
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\times{2^n})$
• 空間複雜度：$O(n)$