【ITニュース解説】Subsets

与えられた整数の集まり、すなわち配列（vector<int>）から、その「部分集合」をすべて見つけ出す問題は、プログラミングの分野でよく遭遇する基本的な課題の一つだ。部分集合とは、元の集まりからいくつかの要素（0個でも構わない）を選び出して作られる新しい集まりを指す。例えば、{1, 2}という配列がある場合、その部分集合は{}（空の集合）、{1}、{2}、{1, 2}の四つになる。システム開発において、データの組み合わせを考えたり、可能な選択肢をすべて洗い出したりする場面は多く、部分集合を効率的に生成する技術は、アルゴリズムの基礎として非常に重要だ。特に、探索や最適化の問題を解く上で、この考え方は頻繁に用いられる。

この問題に対する解決策として、記事では主に二つの異なるプログラミングアプローチが示されている。「反復（Iterative）」と「再帰（Recursive）」だ。それぞれについて詳しく見ていこう。

まず、「反復」アプローチから解説する。この方法は、私たちが普段よく使うループ処理を用いて部分集合を段階的に生成していく方法だ。考え方は、まず空の部分集合だけを結果のリストに用意するところから始める。そして、元の配列の要素を一つずつ取り出し、現在までに生成されているすべての部分集合に対して、その新しい要素を追加した新しい部分集合を作成し、それを結果のリストに加えていく、という流れで処理を進める。

具体的な処理の様子を追ってみよう。もし元の配列がnums = {1, 2, 3}だったとする。

1. 初期状態: 結果を格納するansというリストには、空の部分集合{}だけが含まれている状態だ。つまり、ans = {{}}となる。
2. 最初の要素1を処理: numsから最初の要素である1を取り出す。現在ansにある既存の部分集合は{}一つだけだ。この{}に1を追加した新しい部分集合{1}を生成し、ansに加える。結果、ans = {{}, {1}}となる。
3. 次の要素2を処理: numsから次の要素である2を取り出す。現在ansには{}と{1}という二つの部分集合がある。これらそれぞれに2を追加する。{}からは{2}が、{1}からは{1, 2}が新しく生成される。これらの新しい部分集合をansに加える。結果、ans = {{}, {1}, {2}, {1, 2}}となる。
4. 最後の要素3を処理: numsから最後の要素である3を取り出す。現在ansには{}, {1}, {2}, {1, 2}という四つの部分集合がある。これらそれぞれに3を追加する。それぞれから{3}, {1, 3}, {2, 3}, {1, 2, 3}が新しく生成される。これらの新しい部分集合をansに加える。結果、ans = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3}}となり、すべての部分集合が生成された。

このように、元の配列の要素を一つずつ処理するごとに、既存の部分集合を「増殖」させるようにしてすべての部分集合を作り出していく。コード内では、ansというvector<vector<int>>型の変数がこれまでに生成された部分集合をすべて保持し、numが現在処理中の要素、sizeがループの回数を決定する。ssは既存の部分集合を一時的にコピーして新しい要素を追加するために使われている。

次に、「再帰」アプローチについて見ていこう。再帰とは、関数が自分自身を呼び出すことで処理を繰り返すプログラミングの手法だ。このアプローチでは、「現在の要素を部分集合に含めるか、含めないか」という二つの選択肢を繰り返すことで部分集合を構築するという考え方を用いる。これは、人間の思考に近い自然なアプローチと言えるかもしれない。

このアプローチでは、createSubsetという補助関数が中心的な役割を果たす。この関数は、現在注目している元の配列の要素の位置を示すインデックスと、現在構築中の部分集合（subset）を受け取って処理を進める。

1. 処理の終了条件（ベースケース）: 再帰処理には必ず終了条件が必要だ。もし、すべての要素（配列の最後まで）を処理し終えた場合、その時点でsubsetに入っている要素の組み合わせが一つ完成した部分集合なので、それを最終結果を格納するresというリストに追加して関数の実行を終了する。
2. 再帰的な選択: まだ処理すべき要素が残っている場合、現在の要素nums[index]に対して二つの選択肢を試みる。
   • 現在の要素を「含める」場合: まず、現在構築中の部分集合subsetに現在の要素nums[index]を追加する。この状態で、次の要素index+1についてcreateSubset関数を再び呼び出す。これにより、現在の要素を含んだ状態での部分集合の構築がさらに深められる。
   • 現在の要素を「含めない」場合: 「含める」選択肢の処理が完了し、その先の再帰呼び出しから戻ってきた後、今度は現在の要素を「含めない」場合を試す。そのため、先ほどsubsetに追加したnums[index]をpop_back()（末尾要素の削除）で削除し、subsetを元の状態に戻す。この操作は「バックトラック」と呼ばれ、異なる選択肢を試す際に状態を元に戻すために重要だ。そして、この状態（現在の要素を含まない状態）で、次の要素index+1についてcreateSubset関数を再び呼び出す。

このように、各要素について「含めるか」「含めないか」の二通りの道を探索し、それぞれの道でさらに次の要素に対する選択を繰り返すことで、最終的に考えられるすべての部分集合が生成される。subsets関数は、createSubset関数を最初のインデックス0と空の部分集合から呼び出すことで、この再帰処理を開始する。最終的な結果はresというvector<vector<int>>型の変数に格納される。

「反復」と「再帰」は、同じ部分集合生成の問題を解決するが、アプローチが異なる。反復アプローチは、ループ構造を明示的に使用するため、処理の流れが直線的で直感的に理解しやすい場合が多い。特に、要素が一つ増えるごとに既存の部分集合がどのように変化・増加していくかを具体的にイメージしやすい。コードの記述も比較的シンプルにまとまる傾向がある。

一方、再帰アプローチは「現在の要素を含めるか、含めないか」という二者択一の判断を繰り返すことで問題全体を解決するという、より抽象的な思考に基づいている。そのため、コードは非常に簡潔に書けることが多いが、再帰呼び出しの仕組みや、関数がどのように呼び出され、値がどのように伝達されていくかを理解するには、慣れが必要となる。特に、pop_back()のような「元に戻す」操作（バックトラッキング）は、再帰アルゴリズムの重要な要素だ。再帰は、探索や木構造の操作など、問題の構造が再帰的である場合に非常に強力なツールとなる。どちらのアプローチも最終的な結果は同じだが、処理のイメージやコードの書き方、また特定の条件下でのパフォーマンス特性が異なるため、問題や個人の好みによって使い分けられる。

部分集合の生成という問題は、一見単純に見えるかもしれないが、プログラミングにおける基本的な「組み合わせの生成」や「探索」の考え方を学ぶ上で非常に優れた題材だ。反復と再帰という二つの異なる思考法で同じ問題を解決する過程を通じて、アルゴリズム設計の基礎や、C++言語におけるvectorのような動的な配列の効率的な使い方を深く理解できるだろう。システムエンジニアを目指す上で、このような基礎的な問題を多角的に分析し、解決する能力は、複雑なシステムを設計・実装する上での確かな土台となる。