https://www.ap-siken.com/kakomon/29_haru/pm03.html
問4で解説が理解できません。
解説にあるようにnが4つの場合、状態が2の4乗であることは理解できましたが、プログラムではデキューによる状態の取り出しをしており、最大で16（2の4乗）の状態がメモリに埋まることはないと考えているのですが、なにか誤解しているのでしょうか。
ご教示お願いいたします。

図1をもとにキューの中身をトレースしてみてください。
以下、左をキューの先頭（取り出す側）、右をキューの末尾（格納する側）とします。

まず、初期状態Aがキューに入ります（手順１）。
A
キューからAを取り出します（手順２）。
（キューは空）
次の数を選択した状態B、次の数を選択しない状態Cをキューに入れます（手順３）。
B C
以下、手順２、３の繰り返しです。
キューからBを取り出し、次の状態D、Eをキューに入れます。
C D E
キューからCを取り出し、次の状態F、Gをキューに入れます。
D E F G

このように、ツリー上に並んだ各状態を１段ずつ、左から調べていくことになります。
（アルゴリズムの世界では幅優先探索（BFS）と呼ばれるものです。）

n=4とすると、初期状態を含めて全部で5段のツリーが形成されますが、
4段目をすべて処理し、5段目を1つも処理していないタイミングで、2^4=16個の状態がキューの中に入ることになります。
※図１でいうと、Gの右下の状態をキューから取り出し、そのさらに下の２つの状態をキューに入れたタイミングです。