一、棧回溯的概念：

棧回溯就是回溯法，是一個既帶有系統性又帶有跳躍性的的搜尋演算法。它在包含問題的所有解的解空間樹中，按照深度優先的策略，從根結點出發搜尋解空間樹。演算法搜尋至解空間樹的任一結點時，總是先判斷該結點是否肯定不包含問題的解。如果肯定不包含，則跳過對以該結點為根的子樹的系統搜尋，逐層向其祖先結點回溯。否則，進入該子樹，繼續按深度優先的策略進行搜尋。回溯法在用來求問題的所有解時，要回溯到根，且根結點的所有子樹都已被搜尋遍才結束。而回溯法在用來求問題的任一解時，只要搜尋到問題的一個解就可以結束。這種以深度優先的方式系統地搜尋問題的解的演算法稱為回溯法，它適用於解一些組合數較大的問題。

二、演算法框架：

1、問題的解空間：應用回溯法解問題時，首先應明確定義問題的解空間。問題的解空間應到少包含問題的一個（最優）解。

2、回溯法的基本思想：確定瞭解空間的組織結構後，回溯法就從開始結點（根結點）出發，以深度優先的方式搜尋整個解空間。這個開始結點就成為一個活結點，同時也成為當前的擴充套件結點。在當前的擴充套件結點處，搜尋向縱深方向移至一個新結點。這個新結點就成為一個新的活結點，併成為當前擴充套件結點。如果在當前的擴充套件結點處不能再向縱深方向移動，則當前擴充套件結點就成為死結點。換句話說，這個結點不再是一個活結點。此時，應往回移動（回溯）至最近的一個活結點處，並使這個活結點成為當前的擴充套件結點。回溯法即以這種工作方式遞迴地在解空間中搜索，直至找到所要求的解或解空間中已沒有活結點時為止。

運用回溯法解題通常包含以下三個步驟：

（1）針對所給問題，定義問題的解空間；

（2）確定易於搜尋的解空間結構；

（3）以深度優先的方式搜尋解空間，並且在搜尋過程中用剪枝函式避免無效搜尋。