すべての部分集合を生成する
各要素を選ぶかスキップします
「すべての部分集合を生成する」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
部分集合を生成する理由
競技プログラミングでは、小さな集合のすべての部分集合を試す問題がよく出題されます。再帰を使えば、それらをすっきりと確実に列挙できます。🧩
各要素を選ぶかスキップする
基本的な考え方は、各要素について、含めるか除外するかという二択を行うことです。すべての選択を終えると、1つの部分集合になります。
部分集合はいくつあるか
n個の要素からなる集合には、ちょうど2のn乗個の部分集合があります。各要素によって個数が2倍になるためです。そのため、nは20以下程度の小さな値に抑えます。
再帰的な計画
配列上でインデックスを進めます。各インデックスで、要素を選ぶ分岐とスキップする分岐の2つに分けます。
ベースケース
インデックスが最後の要素を通り過ぎたら、現在の選択経路が1つの完全な部分集合になっています。その時点をベースケースとして記録します。
コードで部分集合を再帰的に生成する
この再帰的な走査では、最後に部分集合を記録してから、各インデックスでスキップする分岐と選ぶ分岐を調べます。
def gen(i, cur):
if i == len(a):
out.append(cur[:])
return
gen(i + 1, cur)
gen(i + 1, cur + [a[i]])元に戻してバックトラックする
要素を追加したら、再帰呼び出しの後でその要素を削除し、次の分岐がきれいな状態から始まるようにします。この取り消しの処理がバックトラッキングの中心です。
cur.append(a[i])
gen(i + 1, cur)
cur.pop()ビットマスクという別の方法
0から2のn乗−1までの各整数を1つの部分集合に対応させる方法もあります。各ビットが、対応する要素を含めるかどうかを表します。
for mask in range(1 << n):
sub = [a[i] for i in range(n) if mask >> i & 1]保存する前にコピーする
現在のリストそのものではなく、必ずそのコピーを保存します。そうしないと、後の変更によって保存したすべての部分集合が上書きされます。⚠️
組み合わせを生成する
サイズが固定されたk個の部分集合を得るには、選んだ個数がkに達した時点でその分岐を止めます。これにより、部分集合の生成が組み合わせの生成になります。
部分集合が使われる場面
部分集合の列挙は、小規模なナップサック問題、チーム選び、そして考えられるすべての選択を試す必要がある実現可能性の確認に使えます。
クイックチェック
n個の要素からなる集合には、部分集合がいくつありますか？
まとめ：すべての要素で分岐する
各要素を選ぶかスキップし、各分岐の後で元に戻すことで、すべての部分集合を列挙する方法を学びました。個数は2のn乗になるため、nは小さく保ちます。🎯
よくある質問
「すべての部分集合を生成する」レッスンは無料ですか？
はい。「すべての部分集合を生成する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「すべての部分集合を生成する」で何を学びますか？
各要素を選ぶかスキップします ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「すべての部分集合を生成する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。