基本認識
回溯算法（DFS 深度優(yōu)先算法）實際上一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試過程中尋找問題的解盏阶，當發(fā)現(xiàn)已不滿足求解條件時晒奕，就“回溯”返回，嘗試別的路徑名斟∧曰郏回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索砰盐，以達到目標闷袒。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標岩梳，就退回一步重新選擇囊骤，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”冀值。
基本思想與原理
回溯法（DFS 深度優(yōu)先算法）簡單來說就是按照深度優(yōu)先的順序也物，窮舉所有可能性的算法，但是回溯算法比暴力窮舉法更高明的地方就是回溯算法可以隨時判斷當前狀態(tài)是否符合問題的條件列疗。一旦不符合條件滑蚯，那么就退回到上一個狀態(tài)，省去了繼續(xù)往下探索的時間。
換句話說告材，回溯法可以理解為通過選擇不同的岔路口尋找目的地坤次，一個岔路口一個岔路口的去嘗試找到目的地。如果走錯了路斥赋，繼續(xù)返回來找到岔路口的另一條路缰猴，直到找到目的地。省去了在錯路上走下去的時間疤剑。
適用的問題
如果一個問題是搜索求解類的問題滑绒，而且該問題的解是樹狀結(jié)構(gòu)（不斷擴張式向量），該題就可以考慮使用回溯算法骚露。
加粗樣式
求解的步驟與模板
回溯函數(shù)的三個組成部分：
1.回溯出口：當找到了一個問題的解時蹬挤，存儲該解。
2.回溯主體：就是遍歷當前的狀態(tài)的所有子節(jié)點棘幸，并判斷下一個狀態(tài)是否是滿足問題條件的焰扳，如果滿足問題條件，那么進入下一個狀態(tài)误续。
3.狀態(tài)返回：如果當前狀態(tài)不滿足條件吨悍，那么返回到前一個狀態(tài)。
回溯函數(shù)萬能模板：
以python3為例：
def backtrack ( 參數(shù) ):
#回溯出口
if ( 滿足題意了 ):
計數(shù)或進行其他操作
return True #有時可以省略
#回溯主體
for( 查找當前節(jié)點的周圍的節(jié)點 )
進行其他的操作;
標記已經(jīng)搜索過的節(jié)點
backtrack( 下一次搜索的節(jié)點 )
#狀態(tài)返回
取消標記;
return False #有時可以省略
引例部分
八皇后問題：
八皇后問題是一個古老而著名的問題蹋嵌，是回溯算法的典型案例育瓜。該問題是國際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊栽烂，即任意兩個皇后都不能處于同一行躏仇、同一列或同一斜線上，問有多少種擺法腺办？
解題思路：
1.從棋盤的第一行開始焰手，從第一個位置開始，依次判斷當前位置是否能夠放置皇后怀喉，判斷的依據(jù)為：同該行之前的所有行中皇后的所在位置進行比較书妻，如果在同一列，或者在同一條斜線上（斜線有兩條躬拢，為正方形的兩個對角線）躲履，都不符合要求，繼續(xù)檢驗后序的位置聊闯。
2.如果該行所有位置都不符合要求工猜，則回溯到前一行，改變皇后的位置菱蔬，繼續(xù)試探域慷。
3.如果試探到最后一行，所有皇后擺放完畢，則直接打印出 8*8 的棋盤犹褒。最后一定要記得將棋盤恢復(fù)原樣，避免影響下一次擺放弛针。
實戰(zhàn)部分
組合總數(shù)Ⅱ問題：
解題思路：
這道題的思路是：以 target 為根結(jié)點叠骑，依次減去數(shù)組中的數(shù)字，直到小于0或者等于0削茁，把等于0的結(jié)果記錄到結(jié)果集中宙枷。
“解集不能包含重復(fù)的組合”，就提示我們得對數(shù)組先排個序（“升序”或者“降序”均可茧跋，下面示例中均使用“升序”）慰丛。
“candidates 中的每個數(shù)字在每個組合中只能使用一次”，那就按照順序依次減去數(shù)組中的元素瘾杭，遞歸求解即可：遇到0就結(jié)算且回溯诅病，遇到負數(shù)也回溯。
candidates 中的數(shù)字可以重復(fù)粥烁，可以借助「LeetCode」第 47 題：“全排列 II”（后面刷題練習(xí)部分有鏈接） 的思想贤笆，在搜索的過程中，找到可能發(fā)生重復(fù)結(jié)果的分支讨阻，把它剪去芥永。
下面附上Python3的題解代碼
class Solution:
def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:
l=len(candidates)
if l==0:
return []
candidates.sort() #初始化
path=[]
res=[]
def backtrack(begin,path,target):
if target==0: #回溯出口
res.append(path[:])
for i in range(begin,l): #回溯主體
target_next=target-candidates[i] #剪枝操作
if target_next<0:
break
if i>begin and candidates[i-1]==candidates[i]:
continue
path.append(candidates[i])
backtrack(i+1,path,target_next)
path.pop() #狀態(tài)返回
backtrack(0,path,target)
return res
趁熱打鐵 刷題練習(xí)部分（持續(xù)更新）
以下是LeetCode題庫中一些用到回溯算法的經(jīng)典例題的題目及解析，有題干钝吮，有題解代碼埋涧、有解題思路（持續(xù)更新）：
No.17.電話號碼的字母組合：
https://blog.csdn.net/LanXiu_/article/details/104085787
No.22.括號生成:
https://blog.csdn.net/LanXiu_/article/details/104103922
No.37.解數(shù)獨:
https://blog.csdn.net/LanXiu_/article/details/104176266
No.39.組合總和:
https://blog.csdn.net/LanXiu_/article/details/104176266
No.40.組合總和Ⅱ:
https://blog.csdn.net/LanXiu_/article/details/104176266
No.44.通配符匹配:
https://blog.csdn.net/LanXiu_/article/details/104177349
No.46.全排列:
https://blog.csdn.net/LanXiu_/article/details/104177432
No.47.全排列Ⅱ:
https://blog.csdn.net/LanXiu_/article/details/104177432
