バックトラッキング とは？

全探索はすべての組み合わせを試す。バックトラッキングは途中で「この先は条件を満たさない」と判断したら、その枝を丸ごとスキップ（枝刈り）する。数独で1マスに数字を入れてルール違反なら即座に戻って別の数字を試す。全パターンを試すより大幅に速くなるんだよ

再帰関数で実装するのが定番。①候補を1つ選んで状態を更新、②制約を満たすか確認、③満たすなら再帰で次の要素へ、④満たさないなら状態を元に戻して次の候補を試す。「選ぶ→進む→ダメなら戻す」のパターン。状態を元に戻す処理が重要だからundo操作を忘れずにね

①できるだけ早い段階で不可能な枝を切る（制約伝播）、②選択肢が少ないものから先に決める（Most Constrained Variable）、③対称性を利用して重複探索を避ける。N-Queen問題なら行ごとに1つずつクイーンを置くことで探索空間を減らせる。枝刈りの良し悪しで実行時間が桁違いに変わるよ

①正規表現エンジンの内部（NFAのバックトラック実装）、②コンパイラの構文解析、③スケジューリング問題（会議室の割り当て等）、④パズルゲームのソルバー。競技プログラミングでは順列生成、部分和問題、グラフの彩色問題で頻出。再帰とスタックの理解があれば実装は難しくないよ