題型一：排列、組合、子集相關(guān)問題

提示：這部分練習(xí)可以幫助我們熟悉「回溯算法」的一些概念和通用的解題思路。解題的步驟是：先畫圖，再編碼。去思考可以剪枝的條件，?為什么有的時(shí)候用?used?數(shù)組，有的時(shí)候設(shè)置搜索起點(diǎn)?begin?變量，理解狀態(tài)變量設(shè)計(jì)的想法。

• 46. 全排列（中等）
• 47. 全排列 II（中等）：思考為什么造成了重復(fù)，如何在搜索之前就判斷這一支會(huì)產(chǎn)生重復(fù)；
• 39. 組合總和（中等）
• 40. 組合總和 II（中等）
• 77. 組合（中等）
• 78. 子集（中等）
• 90. 子集 II（中等）：剪枝技巧同 47 題、39 題、40 題；
• 60. 第 k 個(gè)排列（中等）：利用了剪枝的思想，減去了大量枝葉，直接來到需要的葉子結(jié)點(diǎn)；
• 93. 復(fù)原 IP 地址（中等）

題型二：Flood Fill

提示：Flood 是「洪水」的意思，Flood Fill 直譯是「泛洪填充」的意思，體現(xiàn)了洪水能夠從一點(diǎn)開始，迅速填滿當(dāng)前位置附近的地勢(shì)低的區(qū)域。類似的應(yīng)用還有：PS 軟件中的「點(diǎn)一下把這一片區(qū)域的顏色都替換掉」，掃雷游戲「點(diǎn)一下打開一大片沒有雷的區(qū)域」。

下面這幾個(gè)問題，思想不難，但是初學(xué)的時(shí)候代碼很不容易寫對(duì)，并且也很難調(diào)試。我們的建議是多寫幾遍，忘記了就再寫一次，參考規(guī)范的編寫實(shí)現(xiàn)（設(shè)置?visited?數(shù)組，設(shè)置方向數(shù)組，抽取私有方法），把代碼寫對(duì)。

• 733. 圖像渲染（Flood Fill，中等）
• 200. 島嶼數(shù)量（中等）
• 130. 被圍繞的區(qū)域（中等）
• 79. 單詞搜索（中等）

說明：以上問題都不建議修改輸入數(shù)據(jù)，設(shè)置?visited?數(shù)組是標(biāo)準(zhǔn)的做法?？赡軙?huì)遇到參數(shù)很多，是不是都可以寫成成員變量的問題，面試中拿不準(zhǔn)的記得問一下面試官

題型三：字符串中的回溯問題

提示：字符串的問題的特殊之處在于，字符串的拼接生成新對(duì)象，因此在這一類問題上沒有顯示「回溯」的過程，但是如果使用?StringBuilder?拼接字符串就另當(dāng)別論。
在這里把它們單獨(dú)作為一個(gè)題型，是希望朋友們能夠注意到這個(gè)非常細(xì)節(jié)的地方。

• 17. 電話號(hào)碼的字母組合（中等），題解；
• 784. 字母大小寫全排列（中等）；
• 22. 括號(hào)生成（中等）?：這道題廣度優(yōu)先遍歷也很好寫，可以通過這個(gè)問題理解一下為什么回溯算法都是深度優(yōu)先遍歷，并且都用遞歸來寫。

題型四：游戲問題

回溯算法是早期簡(jiǎn)單的人工智能，有些教程把回溯叫做暴力搜索，但回溯沒有那么暴力，回溯是有方向地搜索?！噶邸股嫌幸恍┖?jiǎn)單的游戲類問題，解決它們有一定的難度，大家可以嘗試一下。

• 51. N 皇后（困難）：其實(shí)就是全排列問題，注意設(shè)計(jì)清楚狀態(tài)變量，在遍歷的時(shí)候需要記住一些信息，空間換時(shí)間；
• 37. 解數(shù)獨(dú)（困難）：思路同「N 皇后問題」；
• 488. 祖瑪游戲（困難）
• 529. 掃雷游戲（困難）