競技プログラミング（AtCoder）初心者が、最初に突き当たる壁になることが多いアルゴリズムのひとつに『bit全探索』があります。
この記事では、その『bit全探索』についてできる限り丁寧に解説をしていきます。
※この記事ではPythonを使った実装を解説していますが、他の言語を使っている方も読むと理解の助けになるはずです。C++でも使える実装は基本編2で解説しています。
記事リンク
1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題を解きます。
質問先など
ご指摘・ご質問はツイッター・マシュマロ・Discordサーバーまでお気軽にどうぞ！
Twitter: u2dayo
マシュマロ： https://marshmallow-qa.com/u2dayo
ほしいものリスト: https://www.amazon.jp/hz/wishlist/ls/2T9IQ8IK9ID19?ref_=wl_share
Discordサーバー（質問や記事の感想・リクエストなどどうぞ！） : https://discord.gg/jZ8pkPRRMT
よかったらLGTMや拡散していただけると喜びます！
bit全探索をやってみよう！
『部分和問題』
$N$ 個の正の整数 $A_1,A_2,\dots,A_N$ が与えられます。
この中からいくつかの整数を選んで、選んだ数を足し合わせた合計が $W$ になる選び方が何通りあるか出力してください。制約
$1\le{N}\le{16}$
$1\le{A_i}\le{100}$
$1\le{W}\le{10000}$入力
入力は以下の形式で標準入力から与えられます。
$N\ \ W$
$A_1\ \ A_2\ \ \dots\ \ A_N$出力
1行で条件を満たす選び方の数を出力してください。
これは部分和問題という有名な問題です。
$N=5,\ A=\{1,2,3,6,8\},\ W=10$ の場合を考えてみます。
$\{2,8\}$ を選ぶと、$2+8=10$ にすることができます。$\{1,2,3\}$ を選んでも $1+2+3=6$ ですからダメです。
今例にあげた選び方・何も選ばない場合を含めて、全部で $2^5=32$ 通りの選び方があります。すべてのありえる選び方を列挙したのが下の図です。（○は使う場合、×は使わない場合をあらわします）。
部分和問題のbit全探索を使った解き方
この問題を解くためには、先ほどの図のように『すべての選び方について選んだ数字を足し合わせた合計を求めて、$W$ ちょうどになる選び方がいくつあるか数える』コードを書けばいいです。つまり
- 『選ぶ』『選ばない』の組み合わせ方、$2^N$ 通りすべてをもれなく列挙する
- それぞれの組み合わせについて、選んだ整数の合計を求めて、$W$ と等しいなら答えに $+1$ する
というコードを実装すればいいです。
実装編
bit全探索で部分和問題を解くコードの方針が立ったので、この問題を解くコードを書いていきましょう。
選び方がわかれば、合計を求めて判定するのは簡単
数字の選び方 $1$ パターンに対して、選んだ数字の合計が $W$ かどうかの判定は簡単にできます。例えば $A_1,A_3,A_5$ を使うと決まっているときは、 $A_1 +A_3+A_5$ を計算して、$W$ と等しいか判定するだけです。
全列挙がむずかしい
難しいのは、選び方の組み合わせを全列挙する方法です。慣れてしまえば毎回同じパターンを書くだけなのですが、慣れるまでが少し大変ですし、タイピング量も多くなりがちです。
普通は大変なのですが、Pythonを使っている方は、標準ライブラリをうまく使うことで、全列挙を簡単に実装することができます。（C++の人は次の章まで待ってね）
Python のbit全探索はitertoolsモジュールのproduct関数を使うと楽！
Pythonでは、itertools モジュールの product 関数を使うと簡単にbit全探索を実装できます。（公式ドキュメントのリンク）
from itertools import product
for pro in product((0, 1), repeat=N):
# proは長さN、各要素が整数 0 か 1 のタプル
このように書くことで、『長さ $N$ 、各要素が 1 か 0 のタプル』としてありえるものを、重複なく $2^N$ 個 全て列挙することができます。
『長さ $N$ 、各要素が 1 か 0 のタプル』とは、たとえば $N=5$ なら (1, 0, 1, 1, 1) などが該当します。そして、このタプルの $i$ 番目の要素が1なら $A_i$ を『選ぶ』、0なら『選ばない』とみなします。
(1, 0, 1, 1, 1)なら、$A_1,A_3,A_4,A_5$ を選んで、 $A_2$ は選ばない、ということです。（先ほどの図の○が1に、×が0に対応しています）
productで生成されるタプルを全部見てみる
repeat=5を指定した次のコードを実行して、生成されるタプルをすべて見てみましょう。
from itertools import product
for pro in product((0, 1), repeat=5):
print(pro)
$2^5=32$ 通りの『長さ $5$ 、各要素が 1 か 0 のタプル』がすべて表示されるはずです。実行してみると、以下の出力を得られます。
(0, 0, 0, 0, 0)
(0, 0, 0, 0, 1)
(0, 0, 0, 1, 0)
(0, 0, 0, 1, 1)
(0, 0, 1, 0, 0)
(0, 0, 1, 0, 1)
(0, 0, 1, 1, 0)
(0, 0, 1, 1, 1)
(0, 1, 0, 0, 0)
(0, 1, 0, 0, 1)
(0, 1, 0, 1, 0)
(0, 1, 0, 1, 1)
(0, 1, 1, 0, 0)
(0, 1, 1, 0, 1)
(0, 1, 1, 1, 0)
(0, 1, 1, 1, 1)
(1, 0, 0, 0, 0)
(1, 0, 0, 0, 1)
(1, 0, 0, 1, 0)
(1, 0, 0, 1, 1)
(1, 0, 1, 0, 0)
(1, 0, 1, 0, 1)
(1, 0, 1, 1, 0)
(1, 0, 1, 1, 1)
(1, 1, 0, 0, 0)
(1, 1, 0, 0, 1)
(1, 1, 0, 1, 0)
(1, 1, 0, 1, 1)
(1, 1, 1, 0, 0)
(1, 1, 1, 0, 1)
(1, 1, 1, 1, 0)
(1, 1, 1, 1, 1)
確かに $2^5=32$ 通りすべての『長さ $5$ 、各要素が 1 か 0 のタプル』を全て列挙できています。（先ほどの画像の○と×に対応しています）
このタプルを判定関数に渡して、選んだ数字の合計が $W$ と等しいか判定するだけです。
コード
慣れている人が見ると、やや冗長な部分に見える部分もあるかもしれませんが、今回はわかりやすさを重視しています。
入力受け取りとインポート
いつもどおり $N,W$ を整数として受け取り、また $N$ 個の整数 $A_i$ をリストで受け取ります。
また、itertoolsモジュールのproduct関数を使うために、from itertools import product と書きます。
from itertools import product
N, W = map(int, input().split())
A = list(map(int, input().split()))
bit全探索の組み合わせを全列挙する部分
product((0, 1), repeat=N)をforループで回して、長さ $N$ の 0 か 1 からなるタプルを、判定関数に $1$ つずつ渡していきます。
ans = 0
for pro in product((0, 1), repeat=N):
ans += judge(pro) # タプルproを渡す judgeは選び方の合計がWなら1, そうでないなら0を返す
print(ans)
判定部分
渡されたタプルをforループで見ていって、$i$ 番目が1ならA[i] を使うので合計に足します。
合計が $W$ ならば $1$ を返して、そうでなければ $0$ を返します。
def judge(pro):
S = 0
for i in range(N):
if pro[i]: # pro[i] が 1 なら A[i] を足す（if文の判定では、0はFalse扱い、他の整数はTrue扱いされます）
S += A[i]
if S == W: # S == W なら +1、そうでなければ 0 を返す
return 1
else:
return 0
全体
from itertools import product # import文は一番上にまとめておくほうが良いです
def judge(pro):
S = 0
for i in range(N):
if pro[i]: # pro[i] が 1 なら A[i] を足す（if文の判定では、0はFalse扱い、他の整数はTrue扱いされます）
S += A[i]
if S == W: # S == W なら +1、そうでなければ 0 を返す
return 1
else:
return 0
N, W = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
for pro in product((0, 1), repeat=N):
ans += judge(pro) # タプルproを渡す judgeは選び方の合計がWなら1, そうでないなら0を返す
print(ans)
実行してみる
サンプル1
入力
5 10
1 2 3 6 8
出力
2
サンプル2
入力
8 1
1 1 1 1 1 1 1 1
出力
8
サンプル3
入力
1 100
100
出力
1
サンプル4
入力
16 34
5 4 8 7 1 6 8 5 9 7 6 7 8 9 4 4
出力
1057
サンプル5
入力
16 234
33 65 52 40 95 30 71 95 45 14 18 48 88 16 76 39
出力
77
おまけ：部分和問題は『動的計画法』でも解ける
完全におまけの話をします。bit全探索よりも難しいアルゴリズムの話なので、今理解する必要はありません。
部分和問題は動的計画法（Dynamic Programming, DP）というアルゴリズムを使って $O(NW)$ の計算量で解くこともできます。$W$ が比較的小さい場合は、 $N$ が大きい場合でも高速に解くことができます。
ただし、例えば $W\le10^{18}$ , $N\le16$ のように$W$ が非常に大きく、$N$ が小さい場合はbit全探索でないと解けません。制約によってアルゴリズムを使い分けるのも重要です。
動的計画法のコード
N, W = map(int, input().split())
A = list(map(int, input().split()))
dp = [[0] * (W + 1) for _ in range(N + 1)]
dp[0][0] = 1
for i, x in enumerate(A):
for j in range(W + 1):
dp[i + 1][j] += dp[i][j]
if j - x >= 0:
dp[i + 1][j] += dp[i][j - x]
print(dp[N][W])
記事リンク（再掲）
1. 入門編 bit全探索ってなに？ : bit全探索はどんなことをするアルゴリズムなのか解説します。
2. 基本編1 簡単な例題でbit全探索をやってみよう！ : 簡単な例題（部分和問題）で実際にbit全探索を実装してみます。
3. 基本編2 2進法を使って実装してみよう！ : 2進法を使ったbit全探索の実装をしてみます。
4. 実践編 AtCoderの問題を解いてみよう！ : AtCoderのbit全探索を使う問題のヒントとコード（Python・C++）を載せています。
5. 応用編 3つ以上の選択肢は再帰関数で書こう！ : 再帰関数を使ってbit全探索に似た問題を解きます。