pythonでのbit全探索

概要

atcoderなどでbit全探索の問題が出た際に、さらっと参照するための備忘録です。
細かなbit全探索の説明は、けんちょんさんの記事やアルゴリズムの解説サイトを見た方が良いと思います。

bit全探索について

bit全探索とは、ある集合{1,2,3,...,N}に対して1を含めるor含めない、2を含めるor含めない…で全通り探索する方法です。
要素１つにつき、含めるor含めないで2通り、集合全体で2^N通りになるため、Nが小さいときに活用できます。
この時、含めるを1で含めないを0で表すことで2進数を用いて簡単に全列挙できる点がポイントです。

使い方

基本的に自分は、集合の部分集合を全列挙する形で活用しています。
非常に基本的な問題として、以下の問題などが分かりやすいかと思います。

引用元：AIZU ONLINE JUDGE

長さ n の数列 A と整数 m に対して、A の要素の中のいくつかの要素を足しあわせて m が作れるかどうかを判定するプログラムを作成してください。A の各要素は１度だけ使うことができます。
数列 A が与えられたうえで、質問として q 個の mi が与えれるので、それぞれについて "yes" または "no" と出力してください。

入力

n
A1 A2 A3 ... An
q
m1 m2 m3 ... mq

sample.py

# 入力の受け取り
n = int(input())
A = list(map(int, input().split()))

q = int(input())
M = list(map(int, input().split()))

# 列挙したものを格納する配列
sum_list = []

# 1を n bit左にシフトし、上限値を1_0*(n-1) にする。
for i in range(1 << n):
  l = []
# iをjbit右にシフトし、1の時だけ配列に格納するようにする
  for j in range(n):
    if i >> j & 1:
      l.append(A[j])
# iのときの配列をもともと設定しておいた配列に格納する
# 今回は和を求めたいため、sumで格納。
  sum_list.append(sum(l))

# 全通り列挙された配列をもとに、回答を表示していく。
for i in range(q):
  if M[i] in sum_list:
    print("yes")
  else:
    print("no")

まとめ

Nが小さいときは、bit全探索を用いて全部列挙しましょう。

なんとなく理解できた方には、@e869120さんが書かれた分野別　初中級者が解くべき過去問精選 100 問で練習すると良いと思います。