部分集合とべき集合
バックトラッキングとビットマスクを使って集合のすべての部分集合を生成し、ソートして重複要素をスキップすることで重複にも対応します。
「部分集合とべき集合」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
部分集合とべき集合
集合 S のべき集合とは、空集合と S 自身を含む、S のすべての部分集合の集合です。n 個の要素を持つ集合には、正確に2ⁿ個の部分集合があります。[1, 2, 3] の8個の部分集合は、[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3] です。これは、考えられるすべての組み合わせ、分割、選択を見つける面接問題で登場する、基本的な組合せ論の問題です。
# A set of n elements → 2^n subsets
for n in range(5):
print(f'n={n}: {2**n} subsets')
# n=0: 1 (just the empty set)
# n=1: 2 ([], [x])
# n=2: 4 ([], [a], [b], [a,b])
# n=3: 8 (as enumerated above)
# n=4: 16バックトラッキングによる部分集合生成
choose-explore-unchoose テンプレートを使います。重要な設計上の判断は、各再帰呼び出しで現在の部分パスを、さらに要素を選ぶ前に結果へ追加することです。これにより、空の状態、途中の状態、完全な状態を含むすべての状態が、有効な部分集合として記録されます。start インデックスを進めて、最後に選んだ要素より右にある要素だけを候補にすることで、重複を防ぎ、順序を維持します。
def subsets(nums):
result = []
def backtrack(start, path):
result.append(list(path)) # every state is a valid subset
for i in range(start, len(nums)):
path.append(nums[i]) # CHOOSE
backtrack(i + 1, path) # EXPLORE (advance start)
path.pop() # UNCHOOSE
backtrack(0, [])
return result
print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]ビットマスクによる方法
バックトラッキングの代わりに、ビットマスクを使う方法があります。各部分集合を n ビットの数値に対応させ、ビット i が1なら要素 i が含まれていることを表します。0 から 2ⁿ - 1 まで反復し、各数値からビットを取り出して部分集合を構築します。これは反復的な方法で、実際にはより高速なことが多く、コードも非常に簡単です。ただし、合計の上限などの制約がある問題には、きれいには一般化できません。
def subsets_bitmask(nums):
n = len(nums)
result = []
for mask in range(1 << n): # 0 to 2^n - 1
subset = []
for i in range(n):
if mask & (1 << i): # bit i is set
subset.append(nums[i])
result.append(subset)
return result
print(subsets_bitmask([1, 2, 3]))
# Same 8 subsets, order may differ部分集合の反復的な生成
反復的な方法では、要素を1つずつ加えてべき集合を構築します。まず [[] ]（空集合）から始めます。新しい要素ごとに、既存の部分集合をすべて複製し、各複製に新しい要素を追加します。n 個の要素を処理すると、結果にはすべての 2ⁿ 個の部分集合が含まれます。これはビットマスクと同等ですが、ビット演算に慣れていない人にとっては、より読みやすい方法です。
def subsets_iterative(nums):
result = [[]] # start with empty set
for num in nums:
# For each existing subset, create a new subset with num added
result += [subset + [num] for subset in result]
return result
print(subsets_iterative([1, 2, 3]))
# After num=1: [[], [1]]
# After num=2: [[], [1], [2], [1,2]]
# After num=3: [[], [1], [2], [1,2], [3], [1,3], [2,3], [1,2,3]]Subsets II：重複の処理
入力に重複が含まれている場合、単純な方法では重複した部分集合が生成されます。[1, 2, 2] では、2つの 2 がそれぞれ独立に [1, 2] を生成してしまいます。解決するには、まず配列をソートし、同じ階層で直前の候補と等しい候補をスキップします。具体的には、ループ内で if i > start and nums[i] == nums[i-1]: continue とします。
def subsets_with_dups(nums):
nums.sort() # sort to group duplicates together
result = []
def backtrack(start, path):
result.append(list(path))
for i in range(start, len(nums)):
# Skip duplicates at the same tree level
if i > start and nums[i] == nums[i-1]:
continue
path.append(nums[i])
backtrack(i + 1, path)
path.pop()
backtrack(0, [])
return result
print(subsets_with_dups([1, 2, 2]))
# [[], [1], [1,2], [1,2,2], [2], [2,2]] — no duplicate subsets重複スキップが機能する理由
条件 i > start and nums[i] == nums[i-1] は、同じ 再帰レベル（同じ start）でのみ重複をスキップします。異なる深さで同じ値を選択することは妨げません。[1, 2, 2] の場合、レベル 0 では最初の 2（インデックス 1）を含め、次のレベル（start=2）で 2 番目の 2 を含めて [2, 2] を作ります。しかし、レベル 0 でもう一度 2 番目の 2 を含めようとすると、この条件に該当してスキップされます。
# Visual: [1, 2, 2] sorted
# Level 0 (start=0): pick nothing, pick 1, pick first-2, pick second-2 (SKIP)
# Level 1 after picking 1 (start=1): pick first-2, pick second-2 (SKIP)
# Level 2 after picking 1,first-2 (start=2): pick second-2
# → [1,2,2] is generated but only once
nums = [1, 2, 2]
nums.sort()
result_set = set(tuple(sorted(s)) for s in subsets_with_dups(nums[:]))
result_naive = set(tuple(sorted(s)) for s in subsets(nums))
print('With dedup:', sorted(result_set))
print('Same results:', result_set == result_naive)
def subsets(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
def subsets_with_dups(nums):
result = []
def bt(start, path):
result.append(list(path))
for i in range(start, len(nums)):
if i > start and nums[i] == nums[i-1]: continue
path.append(nums[i]); bt(i+1, path); path.pop()
bt(0, [])
return result
print(len(subsets_with_dups([1,2,2])), 'unique subsets') # 6固定サイズの部分集合（k-組合せ）
サイズがちょうど k の部分集合だけを生成する場合（LeetCode 77: Combinations）、早期終了条件を追加できます。残りの要素ではパスをサイズ k まで埋められない場合、枝刈りします。枝刈り条件は i > n - (k - len(path)) です。残りの要素数が足りなければ、そこで早期終了します。すべての部分集合を生成してから絞り込む場合と比べて、探索空間を大幅に削減できます。
def combine(n, k):
result = []
def backtrack(start, path):
if len(path) == k:
result.append(list(path))
return
# Prune: need (k - len(path)) more elements from [start..n]
# At most (n - start + 1) elements remain
if n - start + 1 < k - len(path):
return # not enough elements left
for i in range(start, n + 1):
path.append(i)
backtrack(i + 1, path)
path.pop()
backtrack(1, [])
return result
print(combine(4, 2)) # [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
print(len(combine(10, 3))) # C(10,3) = 120冪集合の応用
冪集合のパターンは、面接でよく出るさまざまな派生問題に登場します。(1) 2つの等しい部分集合への分割 — どこかの部分集合の合計が total/2 になるかを確認します。(2) 2つの部分集合の最大 XOR — 部分集合のすべてのペアを試します。(3) k 個の要素を選ぶ最小コスト — k 個の要素からなる部分集合を列挙します。直接列挙すると指数時間になりますが、構造を認識できれば、これらの多くは DP で解決できます。冪集合として捉えることで、最適化する場合でも状態空間を特定しやすくなります。
def max_subset_sum(nums, k):
'''Maximum sum of any k elements (for comparison: O(n log n) alternative)'''
# Backtracking approach: enumerate all k-subsets
max_s = [float('-inf')]
def bt(start, path, curr_sum):
if len(path) == k:
max_s[0] = max(max_s[0], curr_sum)
return
remaining_spots = k - len(path)
for i in range(start, len(nums)):
if len(nums) - i < remaining_spots: break # prune
bt(i+1, path+[nums[i]], curr_sum+nums[i])
bt(0, [], 0)
return max_s[0]
# Much faster: just sort and take top k
def max_subset_sum_fast(nums, k):
return sum(sorted(nums, reverse=True)[:k])
nums = [3, 1, 4, 1, 5, 9, 2, 6]
print(max_subset_sum(nums, 3)) # 20 (9+6+5)
print(max_subset_sum_fast(nums, 3)) # 20部分和の判定
Subset Sum では、配列の部分集合のうち、合計が target になるものが存在するかを問います。バックトラッキング（指数時間）または DP（多項式時間）で解決できます。バックトラッキングによる実装は単純ですが、入力が大きくなると現実的ではありません。DP による実装（ブール値テーブル dp[target+1]）は、面接で推奨されるアプローチです。両方を理解しておくと、バックトラッキングはすべての解を返し、DP は判定問題に効率よく答えられるというトレードオフを説明できます。
# Backtracking version: finds a subset if it exists
def subset_sum_bt(nums, target):
def bt(start, remaining):
if remaining == 0: return True
if remaining < 0 or start == len(nums): return False
# Include nums[start]
if bt(start + 1, remaining - nums[start]): return True
# Exclude nums[start]
return bt(start + 1, remaining)
return bt(0, target)
# DP version: O(n * target) time
def subset_sum_dp(nums, target):
dp = {0}
for num in nums:
dp |= {s + num for s in dp}
return target in dp
print(subset_sum_bt([3, 1, 4, 1, 5], 6)) # True (1+5 or 1+1+4)
print(subset_sum_dp([3, 1, 4, 1, 5], 6)) # True部分集合列挙の計算量
すべての部分集合を生成する場合、時間計算量は避けられず O(n × 2ⁿ) になります。2ⁿ 個の部分集合があり、それぞれの平均サイズが n/2 だからです。すべての部分集合を要求される場合、これより効率のよいアルゴリズムはありません。ある性質（最大の合計など）を持つ部分集合を 1 つだけ求める問題では、DP または貪欲法を優先すべきです。面接で重要なポイントは、すべての部分集合を列挙する必要があるのか、それとも条件を満たす部分集合が1つでも存在するかを調べればよいのかを、必ず確認することです。その答えによって、指数時間が許容されるのか、多項式時間が必要なのかが決まります。
import time
def count_subsets(n):
nums = list(range(n))
result = []
def bt(start, path):
result.append(None) # count without storing
for i in range(start, len(nums)):
path.append(i); bt(i+1, path); path.pop()
bt(0, [])
return len(result)
for n in [10, 15, 20]:
start = time.time()
cnt = count_subsets(n)
elapsed = time.time() - start
print(f'n={n}: {cnt} subsets ({2**n} expected) in {elapsed:.3f}s')3つのアプローチの比較
すべての部分集合を生成する場合、バックトラッキングは最も汎用性が高く、重複や制約にも簡単に対応できます。ビットマスクは簡潔で高速ですが、n ≤ 30（整数のビット幅）に制限されます。反復処理は直感的で、再帰のオーバーヘッドを避けられます。3つとも O(n × 2ⁿ) の出力を生成します。面接では、バックトラッキングによって再帰的な意思決定プロセスを理解していることを示せます。この考え方は、より難しい問題にも応用できます。アプローチを説明する際は、3つすべてに触れるとよいでしょう。
# All three approaches for [1,2,3]
nums = [1, 2, 3]
# 1. Backtracking
def bt(start, path, res):
res.append(list(path))
for i in range(start, len(nums)):
path.append(nums[i]); bt(i+1, path, res); path.pop()
res1 = []; bt(0, [], res1)
# 2. Bit masking
res2 = [[nums[i] for i in range(len(nums)) if mask & (1<<i)]
for mask in range(1<<len(nums))]
# 3. Iterative
res3 = [[]]
for num in nums:
res3 += [s+[num] for s in res3]
print('All produce', len(nums)**2, '-ish subsets:',
len(res1), len(res2), len(res3)) # all 8クイックチェック
このレッスンで学んだ Data Structures & Algorithms — Coding Interview Prep の概念を理解できているか確認しましょう。
レッスンのまとめ
このレッスンでは、バックトラッキングでは、さらに探索する前に各部分パスを結果に追加することで、すべての部分集合を生成すること、重複は配列をソートし、条件 i > start and nums[i] == nums[i-1] を使って同じ再帰の深さで繰り返される値をスキップすることで処理すること、そしてビットマスクでは、各部分集合を一意のビットマスクに対応させることで、簡潔な反復処理による代替手法を実現できることを学びました。次は、異なる制約を持つ関連する列挙問題である Permutations と Combinations に取り組みます。
よくある質問
「部分集合とべき集合」レッスンは無料ですか？
はい。「部分集合とべき集合」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「部分集合とべき集合」で何を学びますか？
バックトラッキングとビットマスクを使って集合のすべての部分集合を生成し、ソートして重複要素をスキップすることで重複にも対応します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「部分集合とべき集合」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。