バックトラッキング
01 / 一文での本質
決定木を深さ優先で探索し、戻り際にそれぞれの選択を取り消す —— こうして同じ配列、同じ再帰フレーム、同じパスが、すべての候補を順に構築する。
問題集合の部分集合をすべて列挙する入力[1, 2, 3]2ⁿ8
出力済み—— まだなし ——
根から開始、部分集合は [ ]。各要素について「含める / 含めない」を決める。
ステップ
0 / 15
深さ
0
現在の部分集合
[ ]
出力済み
0
0 / 15
02 / パターンの骨格
# 決定の木上での DFSbacktrack(state, depth):if 葉に到達、または枝刈り済み:記録 / 破棄して returnfor この深さの各 choice:// 1. 状態を拡張するchoice を state に適用backtrack(state, depth + 1)// 2. 次の兄弟を試す前に取り消すstate から choice を戻す
03 / このパターンを使うべき合図
「すべて / 全列挙」
1 つの最適解ではなく、妥当な配置をすべて列挙する必要がある。 問題が気にしているのは網羅性。
「列を組み立てる」
答えは一連の決定 —— 要素を選ぶ、行を選ぶ、文字を選ぶ —— であり、それらは互いに影響し合う。
「制約を満たす」
途中状態を逐次的に検証できる —— 制約が破られた時点で部分木全体を枝刈りできる。
「階乗 / 指数」
問題文では探索空間が巨大に見えるが、制約のおかげで大半は到達不能 —— 実用的に解けるのは枝刈りのおかげ。
04 / よくある落とし穴
i.
次の兄弟を試す前に選択を取り消すのを忘れる。
バックトラッキングの「バック」こそが見落とされがちな部分。 再帰呼び出しから戻ったあとに
state を復元しないと、 古い状態が兄弟枝に持ち越され —— 誤った部分集合、重複解、あるいは不正な盤面が生まれる。ii.
葉でコピーではなく参照を保存してしまう。
結果を記録するときは、現在の状態の
copy を push すること —— 参照ではダメ。 再帰はこの状態を書き換え続けるので、収集済みの結果も一緒に書き換わってしまう。iii.
早期の枝刈りチェックを忘れる。
素朴な実装は木全体を歩く —— 指数時間。速い実装は下りる前に、 現在の部分状態がまだ妥当な解に至り得るかを確認し、無理なら部分木をまるごと飛ばす。 多くの問題で、枝刈りこそが「速い」と「使い物にならない」の分かれ目になる。
05 / LeetCode で練習
4 問、分岐幅の順に並べた。Subsets は上に示した二分木そのもの。 残りは分岐がより広く、速度を保つには枝刈りが要る。