pythonでのbit全探索 - Qiita

概要 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 の要素の中