狀態空間樹（state-space tree）
當你靠一連串選擇來建構解時，你可以畫出這些選擇能怎麼走的全貌。先放一個「什麼都還沒決定」的節點。從它畫出第一個決定每個選項各一條分支；從那每一條，再畫第二個決定的分支；依此類推。結果就是狀態空間樹：根是空的部分解，每條邊是一個決定，每個節點是一個部分解，每個葉子是一個完整候選。
這棵樹就是把搜尋空間化為一個你能走訪的結構。深度 d 的節點代表一個前 d 個決定已固定的部分解。從根到葉的路徑拼出一整組選擇——一個完整候選。葉子的數目就是搜尋空間的大小：在 n 件物品各分 2 岔，你得到一棵有 2^n 個葉子的樹（子集合）；以「下一個元素是誰」來分岔，你得到 n! 個葉子（排列）。回溯正是這棵樹的深度優先走訪，而「做—遞迴—撤銷」的動作對應於沿一條邊下行、探索子樹、再上行回來。
把狀態空間樹畫出來，正是把一個模糊的暴力法變成你能推理、能加速的方法。剪枝意味著在某個內部節點砍掉一棵子樹——宣告「這個部分解不可能通往任何合法（或任何最佳）葉子」，於是跳過它底下的一切。可行性剪枝砍掉違反約束的子樹；定界（分支定界）砍掉「最好的可能葉子也比已找到的解更差」的子樹。窮舉搜尋的全部藝術，就是在約束允許下，盡量少訪節點地對這棵樹做 DFS。
對 {a, b, c} 的子集合，狀態空間樹在 a（深度 1）分「拿或不拿」、然後 b（深度 2）、然後 c（深度 3）。它的 2^3 = 8 個葉子就是那 8 個子集合。若有約束說最多只能拿一件，那麼「拿了 a 又拿了 b」這個節點不可行——剪掉它，它底下後續選擇的整棵子樹就再也不會被走訪。
根 = 什麼都沒決定；葉 = 什麼都決定了；剪枝在一個不可行的節點砍掉整棵子樹。
狀態空間樹是一張概念地圖，並不是你一口氣在記憶體裡建出來的東西——DFS 一個節點一個節點地走訪它，只用到「根到目前節點」的那條路徑，所以空間成本是樹的深度，而非它（指數級）的節點數。