どの薬品を混ぜてどれを混ぜないかを全て試し、それぞれの混ぜ方について

• 直ちに爆発しないか
• 直ちに爆発しないなら、新たに加えると爆発するような物質の数はいくつか

を計算します。

どの薬品を混ぜてどれを混ぜないかを全て列挙するのは、\(0\) 以上 \(2^N\) 未満の整数を列挙し、その数の \(2\) 進数表記の \(2^i\) の桁が \(1\) である場合、そしてその場合に限って薬品 \(i + 1\) を混ぜるということにすると実装がしやすいです。 (整数の \(2\) 進数表現で \(2^i\) の桁の値を取得するのは、多くの言語で bit 演算子 を使って簡潔に実装することができます)

直ちに爆発するかどうかは、\(M\) 個の爆発する混ぜ方全てについて \(3\) つの薬品が含まれているか試せばよいです。
新たに加えると爆発するような物質の数は、\(M\) 個の爆発する条件のうち、混ぜると爆発する \(3\) つの薬品のうち既に \(2\) つが入っているものについて、残りの一つの薬品にチェックを付けるなどするとよいです。

\(O(1)\) の bit 演算が利用できれば、全体の時間計算量は \(O(2^NM) = O(2^N N^3)\) となります。