\(0, 1, 2\) のみからなる長さ \(N\) の列を全探索する方法について，3 通りの方針を挙げます．

1. DFS を使う方法
2. bit 演算を使う方法
3. ライブラリを使う方法

特に新規性はありませんが，実装の助けになれば幸いです．

DFS を使う方法

空列 \(()\) から始めて，\(0, 1, 2\) のみからなる長さ \(N\) 以下の列を全て作ることを考えます．

列をそのまま頂点に見立てて DFS をしてみます． いま，列 \(X = (X_1, \cdots, X_n)\ (n\le N)\) に対応する頂点にいるとすると，次のような遷移を行えます．

• \(n = N\) のとき：次の探索箇所を探索する．
• \(n\lt N\) のとき：\(X\) の末尾にそれぞれ \(0, 1, 2\) を挿入した列に対し，探索を行う．

この問題では \(n = N\) となった列を列挙すればよいです．

実装例

\(X\) を陽に持たないで探索することもできます． あくまで推測ですが，こちらの方が定数倍が良いと思います．

実装例

この問題では各要素のとる範囲が一定ですが，範囲が一定でない場合にも応用が効くため，汎用性が高いと考えられます．

bit 演算を使う方法

ややトリッキーな方法です．

bit 全探索を行うと，各動物園に \(0\) 回行った，あるいは \(1\) 回行った，という状態を列挙できます． その状態に対し，立っている bit だけでさらに bit 全探索をするようなことを考えると，\(2\) 回行った状態も表現できます．

つまり，ある集合に対してその部分集合を列挙できればよいです． これは例えば ABC269Cの解説 の解法 3 で説明されています．

実装例

余談ですが，この手法を bit DP に応用できる場合があります．

応用例（最小シュタイナー木問題）

応用例（青 diff）

ライブラリを使う方法

言語によってはライブラリを用いて簡潔に書くことができます．

例えば，Python の itertools モジュールには product という関数があります． これを使うと，求めたい列の集合は itertools.product([0, 1, 2], repeat=N) と表現できます．

itertools モジュールには他にも combinations や permutations など，全探索を実装する際に有用な関数が含まれています．