Subsets II - หาสับเซตทั้งหมด (รองรับค่าซ้ำ) ใน C++

ภาพรวมปัญหา

มีชุดตัวเลข (อาจมีค่าซ้ำ) ต้องสร้างทุกสับเซตที่เป็นไปได้ (Power Set) โดยไม่ให้มีสับเซตซ้ำ

ตัวอย่าง: [1,2,2] → [[], [1], [2], [1,2], [2,2], [1,2,2]]

อัลกอริทึม (Recursive + Set เพื่อกันซ้ำ)

1. สร้าง array res และ set x
2. ฟังก์ชัน solve(index, temp, nums):
   • ถ้า index = ขนาด nums: ถ้า temp ไม่อยู่ใน x → ใส่เข้า res และ x, return
   • เรียก solve(index+1, temp, nums) // ไม่เอา nums[index]
   • เพิ่ม nums[index] เข้า temp
   • เรียก solve(index+1, temp, nums) // เอา nums[index]
   • ลบตัวสุดท้ายออกจาก temp (backtrack)
3. ฟังก์ชันหลัก: clear res, x, เรียงลำดับ nums, เรียก solve(0, [], nums), เรียง res, return res

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

void print_vector(vector<vector<int> > v){
    cout << "[";
    for(int i = 0; i < v.size(); i++){
        cout << "[";
        for(int j = 0; j < v[i].size(); j++)
            cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    vector < vector <int> > res;
    set < vector <int> > x;
    static bool cmp(vector <int> a, vector <int> b){ return a < b; }
    void solve(int idx, vector <int> temp, vector <int> &v){
        if(idx == v.size()){
            if(x.find(temp) == x.end()){
                res.push_back(temp);
                x.insert(temp);
            }
            return;
        }
        solve(idx+1, temp, v);
        temp.push_back(v[idx]);
        solve(idx+1, temp, v);
        temp.pop_back();
    }
    vector<vector<int> > subsetsWithDup(vector<int> &a){
        res.clear(); x.clear();
        sort(a.begin(), a.end());
        vector <int> temp;
        solve(0, temp, a);
        sort(res.begin(), res.end(), cmp);
        return res;
    }
};

int main(){
    Solution ob;
    vector<int> v = {1,2,2};
    print_vector(ob.subsetsWithDup(v));
}

Input / Output

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