部分集合の生成
LeetCode 78「Subsets」で全ての部分集合を生成する三手法（インクリメンタル構築、バックトラッキング、ビット演算）を解説する。
一見複雑に見える問題の多くは、「すべての可能性を列挙する」ことで解決できます — すなわち力任せの列挙です。一見すると野蛮に見えますが、最も直接的で信頼性の高い手段であることがよくあります。実際の開発においても、BFS による最短経路探索、バックトラッキングによる解の探索、組み合わせ列挙など、この考え方を避けては通れません。
本稿では力任せ列挙の典型問題である、与えられた集合からすべての部分集合を生成する（Power Set）問題に焦点を当てます。順列や経路探索などの他の問題については、別の機会に改めて取り上げます。
重複要素のない配列 nums が与えられたとき、そのすべての部分集合を出力します — すなわち LeetCode 78 - Subsets です。解の規模は 2^n となるため、どのアルゴリズムでも結果を出力するには少なくとも線形時間を要します。
以下に示す三つの手法で、ほとんどの部分集合生成の要件をカバーできます：インクリメンタル構築法、再帰的バックトラッキング（ビットベクトル法）、ビット演算法（二進数列挙）。元の配列に重複要素が含まれる場合は、生成過程で重複を取り除くか、あらかじめソートして同じ値をスキップすることで対応できます。以下でそのヒントも示します。
空集合から始め、要素を一つ処理するごとに現在の結果セットを複製し、その要素を追加します。最終的に得られる集合の数は倍々に増えていきます。
[1,2,3] を例にとると：
- 初期結果：
[] 1を処理：現在の各集合に1を追加し、[]、[1]を得る2を処理：2を追加し、[]、[1]、[2]、[1,2]を得る3を処理：同様に[]、[1]、[2]、[1,2]、[3]、[1,3]、[2,3]、[1,2,3]を得る
時間計算量は O(n·2^n)、空間計算量は O(2^n) です。
vector<vector<int>> subsets(vector<int> &S) { vector<vector<int>> res(1); sort(S.begin(), S.end()); for (int i = 0; i < S.size(); i++) { int size = res.size(); for (int j = 0; j < size; j++) { res.push_back(res[j]); res.back().push_back(S[i]); } } return res;}入力に重複要素が存在する場合、走査時に今回新たに追加した部分集合の範囲を記録し、新しい部分集合に対してのみ同じ要素を追加することで、重複結果を避けることができます。 全体の追加順序は次の通りです：
[][1][2][1 2][3][1 3][2 3][1 2 3]各要素には「選ぶ / 選ばない」の二つの状態があり、これを二分決定木としてモデル化できます：左部分木は現在の要素を選ぶこと、右部分木は選ばないことを表し、葉ノードがすべての部分集合となります。状態木は以下の通りです：
[] / \ / \ / \ [1] [] / \ / \ / \ / \ [1 2] [1] [2] [] / \ / \ / \ / \ [1 2 3] [1 2] [1 3] [1] [2 3] [2] [3] []コードは次の通りです：
vector<vector<int>> subsets(vector<int> &S) { vector<vector<int>> res; vector<int> path; sort(S.begin(), S.end()); genSubsets(S, 0, path, res); return res;}void genSubsets(vector<int> &S, int pos, vector<int> &path, vector<vector<int>> &res) { res.push_back(path); for (int i = pos; i < S.size(); i++) { if (i > pos && S[i] == S[i - 1]) continue; // 重複要素があればスキップ path.push_back(S[i]); genSubsets(S, i + 1, path, res); path.pop_back(); }}全体の追加順序は次の通りです：
[][1][1 2][1 2 3][1 3][2][2 3][3]集合の各要素には「選ぶ / 選ばない」の二つの状態しかなく、二進数のビットと一対一に対応します。長さ n の集合を 0 ~ (1<<n)-1 の二進数にマッピングすることで、すべての部分集合を列挙できます。以下の表は [1,2,3] のマッピング関係を示しています：
| 1 | 2 | 3 | 部分集合 | |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | [] |
| 1 | 0 | 0 | 1 | [3] |
| 2 | 0 | 1 | 0 | [2] |
| 3 | 0 | 1 | 1 | [2,3] |
| 4 | 1 | 0 | 0 | [1] |
| 5 | 1 | 0 | 1 | [1,3] |
| 6 | 1 | 1 | 0 | [1,2] |
| 7 | 1 | 1 | 1 | [1,2,3] |
対応するコードは次の通りです：
vector<vector<int>> subsets(vector<int> &S) { vector<vector<int>> res; sort(S.begin(), S.end()); int total = 1 << S.size(); for (int mask = 0; mask < total; mask++) { vector<int> subset; for (int i = 0; i < S.size(); i++) { if ((mask >> i) & 1) { subset.push_back(S[i]); } } res.push_back(move(subset)); } return res;}- 三つの手法の時間計算量はいずれも
O(n · 2^n)であり、違いは主に実装方法と定数項にあります； - インクリメンタル構築は反復実装に適し、バックトラッキングは枝刈りや条件追加が容易で、ビット演算は低レイヤーの性能最適化に適しています；
- 重複要素を含む集合を扱う際は、事前にソートし、生成過程で重複値をスキップすることを忘れないでください；
- 関連問題への応用も可能です：固定長の部分集合の取得、制約を満たす部分集合の探索（バックトラッキング時の事前枝刈り）、個数の計数など。
力任せの列挙は粗雑であることを意味しません。状態と枝刈り戦略を適切に設計すれば、2^n の探索空間の中でも素早く答えを見つけることができます。