回溯法又稱試探法。回溯法的基本做法是深度優先搜尋，是一種組織得井井有條的、能避免不必要重複搜尋的窮舉式搜尋演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
當我們遇到某一類問題時，它的問題可以分解，但是又不能得出明確的動態規劃或是遞迴解法，此時可以考慮用回溯法解決此類問題。回溯法的優點在於其程式結構明確，可讀性強，易於理解，而且透過對問題的分析可以大大提高執行效率。但是，對於可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。
對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。透過深度優先搜尋這棵樹，列舉每種可能的解的情況；從而得出結果。但是，回溯法中透過構造約束函式，可以大大提升程式效率，因為在深度優先搜尋的過程中，不斷的將每個解（並不一定是完整的，事實上這也就是構造約束函式的意義所在）與約束函式進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。
回溯法中，首先需要明確下面三個概念：
（一）約束函式：約束函式是根據題意定出的。透過描述合法解的一般特徵用於去除不合法的解，從而避免繼續搜尋出這個不合法解的剩餘部分。因此，約束函式是對於任何狀態空間樹上的節點都有效、等價的。
（二）狀態空間樹：剛剛已經提到，狀態空間樹是一個對所有解的圖形描述。樹上的每個子節點的解都只有一個部分與父節點不同。
（三）擴充套件節點、活結點、死結點：所謂擴充套件節點，就是當前正在求出它的子節點的節點，在深度優先搜尋中，只允許有一個擴充套件節點。活結點就是透過與約束函式的對照，節點本身和其父節點均滿足約束函式要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
利用回溯法解題的具體步驟
首先，要透過讀題完成下面三個步驟：
(1)描述解的形式，定義一個解空間，它包含問題的所有解。
(2)構造狀態空間樹。
(3)構造約束函式（用於殺死節點）。
然後就要透過深度優先搜尋思想完成回溯，完整過程如下：
(1)設定初始化的方案（給變數賦初值，讀入已知資料等）。
(2)變換方式去試探，若全部試完則轉(7)。
(3)判斷此法是否成功（透過約束函式），不成功則轉(2)。
(4)試探成功則前進一步再試探。
(5)正確方案還未找到則轉(2)。
(6)已找到一種方案則記錄並列印。
(7)退回一步（回溯），若未退到頭則轉(2)。
(8)已退到頭則結束或列印無解
回溯法又稱試探法。回溯法的基本做法是深度優先搜尋，是一種組織得井井有條的、能避免不必要重複搜尋的窮舉式搜尋演算法。
回溯演算法的基本思想是：從一條路往前走，能進則進，不能進則退回來，換一條路再試。
當我們遇到某一類問題時，它的問題可以分解，但是又不能得出明確的動態規劃或是遞迴解法，此時可以考慮用回溯法解決此類問題。回溯法的優點在於其程式結構明確，可讀性強，易於理解，而且透過對問題的分析可以大大提高執行效率。但是，對於可以得出明顯的遞推公式迭代求解的問題，還是不要用回溯法，因為它花費的時間比較長。
對於用回溯法求解的問題，首先要將問題進行適當的轉化，得出狀態空間樹。這棵樹的每條完整路徑都代表了一種解的可能。透過深度優先搜尋這棵樹，列舉每種可能的解的情況；從而得出結果。但是，回溯法中透過構造約束函式，可以大大提升程式效率，因為在深度優先搜尋的過程中，不斷的將每個解（並不一定是完整的，事實上這也就是構造約束函式的意義所在）與約束函式進行對照從而刪除一些不可能的解，這樣就不必繼續把解的剩餘部分列出從而節省部分時間。
回溯法中，首先需要明確下面三個概念：
（一）約束函式：約束函式是根據題意定出的。透過描述合法解的一般特徵用於去除不合法的解，從而避免繼續搜尋出這個不合法解的剩餘部分。因此，約束函式是對於任何狀態空間樹上的節點都有效、等價的。
（二）狀態空間樹：剛剛已經提到，狀態空間樹是一個對所有解的圖形描述。樹上的每個子節點的解都只有一個部分與父節點不同。
（三）擴充套件節點、活結點、死結點：所謂擴充套件節點，就是當前正在求出它的子節點的節點，在深度優先搜尋中，只允許有一個擴充套件節點。活結點就是透過與約束函式的對照，節點本身和其父節點均滿足約束函式要求的節點；死結點反之。由此很容易知道死結點是不必求出其子節點的（沒有意義）。
利用回溯法解題的具體步驟
首先，要透過讀題完成下面三個步驟：
(1)描述解的形式，定義一個解空間，它包含問題的所有解。
(2)構造狀態空間樹。
(3)構造約束函式（用於殺死節點）。
然後就要透過深度優先搜尋思想完成回溯，完整過程如下：
(1)設定初始化的方案（給變數賦初值，讀入已知資料等）。
(2)變換方式去試探，若全部試完則轉(7)。
(3)判斷此法是否成功（透過約束函式），不成功則轉(2)。
(4)試探成功則前進一步再試探。
(5)正確方案還未找到則轉(2)。
(6)已找到一種方案則記錄並列印。
(7)退回一步（回溯），若未退到頭則轉(2)。
(8)已退到頭則結束或列印無解