C++で解く「サブセットII」：重複を含む集合のべき集合を生成する方法

問題の概要

数値の集合が与えられたとき、その集合から作れるすべての部分集合（サブセット）を生成することを考えます。この「すべての部分集合の集まり」はべき集合とも呼ばれます。ただし本問題では、要素に重複が含まれる可能性がある点に注意が必要です。

例えば、集合が [1,2,2] の場合、べき集合は次のようになります。

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

アルゴリズムの考え方

この問題は再帰（バックトラッキング）を用いて解きます。各要素について「選ぶ／選ばない」の2択を再帰的に試すことで、すべての部分集合を網羅できます。また、重複する部分集合の登録を防ぐため、セット（set）で既に生成した組み合わせを管理します。

全体の手順は以下の通りです。

• 結果を格納する配列 res と、重複チェック用のセット x を用意します。
• 再帰関数 solve() を定義します。引数は、現在のインデックス・一時配列・元の数値配列（nums）です。

solve() の内部処理は次の通りです。

1. index が配列 v のサイズに達した場合、temp が x に存在しないことを確認し、存在しなければ res と x の両方に挿入して return します。
2. solve(index + 1, temp, v) を呼び出します（v[index] を選ばないケース）。
3. v[index] を temp に追加します。
4. solve(index + 1, temp, v) を呼び出します（v[index] を選ぶケース）。
5. temp から最後の要素を取り除き、状態を元に戻します（バックトラック）。

メイン側の処理は以下の通りです。

• res と x をクリアし、入力配列をソートします。事前にソートしておくと重複要素が隣接するため、同じ組み合わせを効率よく検出できます。
• 空の一時配列 temp を定義し、solve(0, temp, array) を呼び出します。
• 最後に 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;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,2};
    print_vector(ob.subsetsWithDup(v));
}

入力

[1,2,2]

出力

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

計算量の目安

要素数を n とすると、部分集合は最大 2^n 個生成されます。そのため、時間計算量は O(2^n × n)、必要な記憶領域も O(2^n × n) 程度になります。セットによる重複チェックには追加のコストがかかりますが、n が小規模な範囲であれば十分実用的です。