332.重新安排行程

51.?N皇后?

37.?解數(shù)獨(dú)?

一刷略過(guò)

看下回溯的總結(jié)：

回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯，所以回溯法也經(jīng)常和二叉樹(shù)遍歷，深度優(yōu)先搜索混在一起，因?yàn)檫@兩種方式都是用了遞歸。

回溯法就是暴力搜索，并不是什么高效的算法，最多再剪枝一下。

回溯算法能解決如下問(wèn)題：

組合問(wèn)題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合

排列問(wèn)題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式

切割問(wèn)題：一個(gè)字符串按一定規(guī)則有幾種切割方式

子集問(wèn)題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集

棋盤(pán)問(wèn)題：N皇后，解數(shù)獨(dú)等等

回溯模板：

void backtracking(參數(shù)) {

? ? if (終止條件) {

? ? ? ? 存放結(jié)果;

? ? ? ? return;

? ? }

? ? for (選擇：本層集合中元素（樹(shù)中節(jié)點(diǎn)孩子的數(shù)量就是集合的大?。? {

? ? ? ? 處理節(jié)點(diǎn);

? ? ? ? backtracking(路徑，選擇列表); // 遞歸

? ? ? ? 回溯，撤銷(xiāo)處理結(jié)果

? ? }

}