332.重新安排行程（二刷回看）
思路：
用回溯記錄可能的行程，用vector<bool>used記錄是否使用過,用如下代碼判斷是否放進(jìn)path:
if(tickets[i][0]!=path.back())
????????????????continue;
????????????if(used[i]==true)
????????????????continue;
注意中止條件是
if(path.size()==(tickets.size()+1))
????????{
????????????result.push_back(path);
????????????return;
????????}
搜索所有路徑會(huì)超時(shí)推盛，應(yīng)該找如何搜索時(shí)找最優(yōu)解峦阁。
看代碼后：
這道題目有幾個(gè)難點(diǎn)：
1. 一個(gè)行程中，如果航班處理不好容易變成一個(gè)圈耘成，成為死循環(huán)
2. 有多種解法榔昔，字母序靠前排在前面，讓很多同學(xué)望而退步瘪菌，如何該記錄映射關(guān)系呢 撒会？
3. 使用回溯法（也可以說深搜） 的話，那么終止條件是什么呢师妙？
4. 搜索的過程中诵肛，如何遍歷一個(gè)機(jī)場(chǎng)所對(duì)應(yīng)的所有機(jī)場(chǎng)。
這道題難是難在容器的選擇和使用上默穴。
第二問：
一個(gè)機(jī)場(chǎng)映射多個(gè)機(jī)場(chǎng)怔檩，機(jī)場(chǎng)之間要靠字母序排列，一個(gè)機(jī)場(chǎng)映射多個(gè)機(jī)場(chǎng)壁顶，可以使用std::unordered_map珠洗，如果讓多個(gè)機(jī)場(chǎng)之間再有順序的話，就是用std::map 或者std::multimap 或者 std::multiset若专。
在遍歷unordered_map<出發(fā)機(jī)場(chǎng), map<到達(dá)機(jī)場(chǎng), 航班次數(shù)>> targets的過程中，可以使用"航班次數(shù)"這個(gè)字段的數(shù)字做相應(yīng)的增減蝴猪，來標(biāo)記到達(dá)機(jī)場(chǎng)是否使用過了调衰。
如果“航班次數(shù)”大于零膊爪，說明目的地還可以飛，如果“航班次數(shù)”等于零說明目的地不能飛了嚎莉，而不用對(duì)集合做刪除元素或者增加元素的操作米酬。
相當(dāng)于說不刪就做一個(gè)標(biāo)記！
函數(shù)返回值用的是bool趋箩！因?yàn)槲覀冎恍枰业揭粋€(gè)行程赃额，就是在樹形結(jié)構(gòu)中唯一的一條通向葉子節(jié)點(diǎn)的路線.
代碼如下：
unordered_map<string,map<string,int>>?targets;
????bool?backtracking(int?ticketNum,?vector<string>?&result)
????{
????????if(result.size()==ticketNum+1)
????????????return?true;
????????for(pair<const?string,?int>?&target?:?targets[result[result.size()-1]])
????????{
????????????if(target.second?>?0)
????????????{
????????????????result.push_back(target.first);
????????????????target.second--;
????????????????if(backtracking(ticketNum,result))?return?true;
????????????????result.pop_back();
????????????????target.second++;
????????????}
????????}
????????return?false;
????}
????vector<string>?findItinerary(vector<vector<string>>&?tickets)?{
????????targets.clear();
????????vector<string>?result;
????????for(const?vector<string>?&?vec:tickets)
????????????targets[vec[0]][vec[1]]++;
????????result.push_back("JFK");
????????backtracking(tickets.size(),result);
????????return?result;
????}
51.N皇后（二刷回看）
思路：
無思路。
看視頻：
畫成樹之后能發(fā)現(xiàn)問題變成了在每一行遍歷回溯每個(gè)節(jié)點(diǎn)是否能放皇后叫确。
定義參數(shù)：
vector<vector<string>>?result;//存放結(jié)果
vector<string>?chessboard(n,?string(n,'.'));//初始化棋盤
void?backtracking(int?n,?int?row,?vector<string>?&chessboard)//n為棋盤邊界跳芳，row為行，傳入棋盤
終止條件：
if(row?==?n)
????????{
????????????result.push_back(chessboard);
????????????return;
????????}//到達(dá)葉子節(jié)點(diǎn)
單層邏輯：
for(int?col=0;col<n;col++)
????????{
????????????if(isValid(row,col,chessboard,n))
????????????{
????????????????chessboard[row][col]?=?'Q';
????????????????backtracking(n,row+1,?chessboard);
????????????????chessboard[row][col]?=?'.';
????????????}
????????}
是否符合條件的判斷：
bool?isValid(int?row,?int?col,?vector<string>?&chessboard,?int?n)
????{
????????for?(int?i?=?0;?i?<?row;?i++)?
????????{
????????????if(chessboard[i][col]==?'Q')
????????????????return?false;
????????}// 同列的情況
????????for(int?i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
????????{
????????????if(chessboard[i][j]==?'Q')
????????????????return?false;
????????}//45°的情況
????????for(int?i=row-1,j=col+1;i>=0?&&?j<n;?i--,j++)
????????{
????????????if(chessboard[i][j]=='Q')
????????????????return?false;
????????}
????????return?true;
????}//135°的情況
37.解數(shù)獨(dú)（二刷回看）
思路：
isValid函數(shù)中：判斷橫豎是否有相同元素竹勉，以及3*3中有沒有相同元素飞盆。
回溯算法中：
中止條件為橫豎都等于9，限制條件是如果元素不是'.'就跳過.但具體回溯不知道怎么寫
看視頻后：
遞歸函數(shù)的返回值需要是bool類型, 因?yàn)橹恍枰业揭粋€(gè)符合的情況就返回
本題遞歸不用終止條件次乓，解數(shù)獨(dú)是要遍歷整個(gè)樹形結(jié)構(gòu)尋找可能的葉子節(jié)點(diǎn)就立刻返回吓歇。
本題是二維遞歸：一個(gè)for循環(huán)遍歷棋盤的行，一個(gè)for循環(huán)遍歷棋盤的列票腰，一行一列確定下來之后城看，遞歸遍歷這個(gè)位置放9個(gè)數(shù)字的可能。
bool?backtracking(vector<vector<char>>&?board)
????{
????????for(int?i=0;i<board.size();i++)
????????{
????????????for(int?j=0;j<board[0].size();j++)
????????????{
????????????????if(board[i][j]!='.')
????????????????????continue;
????????????????for(char?k='1';?k<='9';k++)
????????????????{
????????????????????if(isValid(i,j,k,board))
????????????????????{
????????????????????????board[i][j]=k;
????????????????????????if(backtracking(board))?return?true;
????????????????????????board[i][j]='.';
????????????????????}
????????????????}
????????????????return?false;
????????????}
????????}
????????return?true;
????}
討論是否合法：同行是否重復(fù)杏慰；同列是否重復(fù)测柠；9宮格里是否重復(fù)
bool?isValid(int?row,?int?col,?char?val,?vector<vector<char>>?&board)
????{
????????for(int?i=0;i<9;i++)
????????{
????????????if(board[row][i]==val)
????????????????return?false;
????????}
????????for(int?j=0;j<9;j++)
????????{
????????????if(board[j][col]==val)
????????????????return?false;
????????}
????????int?startRow=(row/3)*3;
????????int?startCol=(col/3)*3;
????????for(int?i=startRow;i<startRow+3;i++)
????????{
????????????for(int?j=startCol;j<startCol+3;j++)
????????????{
????????????????if(board[i][j]==val)
????????????????????return?false;
????????????}
????????}
????????return?true;
????}
回溯總結(jié)：
回溯是遞歸的副產(chǎn)品，只要有遞歸就會(huì)有回溯逃默，因此會(huì)和二叉樹遍歷和深度優(yōu)先搜索結(jié)合鹃愤。
回溯能解決如下問題：
組合問題：N個(gè)數(shù)里面按一定規(guī)則找出k個(gè)數(shù)的集合
排列問題：N個(gè)數(shù)按一定規(guī)則全排列，有幾種排列方式
切割問題：一個(gè)字符串按一定規(guī)則有幾種切割方式
子集問題：一個(gè)N個(gè)數(shù)的集合里有多少符合條件的子集
棋盤問題：N皇后完域，解數(shù)獨(dú)等等
理解回溯應(yīng)該使用樹形結(jié)構(gòu)软吐！
回溯是用遞歸控制for循環(huán)嵌套的數(shù)量：for循環(huán)橫向遍歷，遞歸縱向遍歷吟税，回溯不斷調(diào)整結(jié)果集凹耙。
回溯的優(yōu)化方法只有剪枝！剪枝精髓是：for循環(huán)在尋找起點(diǎn)的時(shí)候要有一個(gè)范圍肠仪，如果這個(gè)起點(diǎn)到集合終止之間的元素已經(jīng)不夠題目要求的k個(gè)元素了肖抱，就沒有必要搜索了。
回溯的模板：
void backtracking(參數(shù)) {
? ? if (終止條件) {
? ? ? ? 存放結(jié)果;
? ? ? ? return;
? ? }
? ? for (選擇：本層集合中元素（樹中節(jié)點(diǎn)孩子的數(shù)量就是集合的大幸炀伞）) {
? ? ? ? 處理節(jié)點(diǎn);
? ? ? ? backtracking(路徑意述，選擇列表); // 遞歸
? ? ? ? 回溯，撤銷處理結(jié)果
? ? }
}
組合問題：
注意startIndex的應(yīng)用：如果是一個(gè)集合來求組合的話，就需要startIndex荤崇，如果是多個(gè)集合取組合拌屏，各個(gè)集合之間相互不影響，那么就不用startIndex术荤。
切割問題：
解決以下問題
1.切割問題其實(shí)類似組合問題
2.如何模擬那些切割線
3.切割問題中遞歸如何終止
4.在遞歸循環(huán)中如何截取子串
5.如何判斷回文
巧用startIndex和i倚喂，注意切割過的地方不能重復(fù)切割所以遞歸函數(shù)需要傳入i + 1。
子集問題：
在樹形結(jié)構(gòu)中子集問題是要收集所有節(jié)點(diǎn)的結(jié)果瓣戚，而組合問題是收集葉子節(jié)點(diǎn)的結(jié)果端圈。
子集問題不需要加終止條件，因?yàn)楸緛砭托枰闅v整棵樹子库。注意遞增子序列這道題舱权。
排列問題：
排列問題不需要startIndex,因?yàn)槊繉佣际菑?開始搜索而不是startIndex。需要used數(shù)組記錄path里都放了哪些元素了刚照。
去重問題：
注意樹層去重和樹枝去重刑巧，可以用used數(shù)組或者set去重，但set效率比較低无畔。組合問題可以抽象為樹形結(jié)構(gòu)啊楚，那么“使用過”在這個(gè)樹形結(jié)構(gòu)上是有兩個(gè)維度的，一個(gè)維度是同一樹枝上“使用過”浑彰，一個(gè)維度是同一樹層上“使用過”恭理。
例如：
used[i - 1] == true，說明同一樹枝candidates[i - 1]使用過
used[i - 1] == false郭变，說明同一樹層candidates[i - 1]使用過
棋盤問題（二刷重點(diǎn)）：
N皇后：棋盤的寬度就是for循環(huán)的長(zhǎng)度颜价，遞歸的深度就是棋盤的高度
解數(shù)獨(dú)：使用二維遞歸，本題中棋盤的每一個(gè)位置都要放一個(gè)數(shù)字诉濒，并檢查數(shù)字是否合法周伦，解數(shù)獨(dú)的樹形結(jié)構(gòu)要比N皇后更寬更深。
性能分析：
子集問題分析：
時(shí)間復(fù)雜度：O(2^n)未荒，因?yàn)槊恳粋€(gè)元素的狀態(tài)無外乎取與不取专挪，所以時(shí)間復(fù)雜度為O(2^n)
空間復(fù)雜度：O(n)，遞歸深度為n片排，所以系統(tǒng)棧所用空間為O(n)寨腔，每一層遞歸所用的空間都是常數(shù)級(jí)別，注意代碼里的result和path都是全局變量率寡，就算是放在參數(shù)里迫卢，傳的也是引用，并不會(huì)新申請(qǐng)內(nèi)存空間冶共，最終空間復(fù)雜度為O(n)
排列問題分析：
時(shí)間復(fù)雜度：O(n!)乾蛤，這個(gè)可以從排列的樹形圖中很明顯發(fā)現(xiàn)每界，每一層節(jié)點(diǎn)為n，第二層每一個(gè)分支都延伸了n-1個(gè)分支幻捏，再往下又是n-2個(gè)分支盆犁，所以一直到葉子節(jié)點(diǎn)一共就是 n * n-1 * n-2 * ..... 1 = n!命咐。
空間復(fù)雜度：O(n)篡九，和子集問題同理。
組合問題分析：
時(shí)間復(fù)雜度：O(2^n)醋奠，組合問題其實(shí)就是一種子集的問題榛臼，所以組合問題最壞的情況，也不會(huì)超過子集問題的時(shí)間復(fù)雜度窜司。
空間復(fù)雜度：O(n)沛善，和子集問題同理。
N皇后問題分析：
時(shí)間復(fù)雜度：O(n!) 塞祈，其實(shí)如果看樹形圖的話金刁，直覺上是O(n^n)，但皇后之間不能見面所以在搜索的過程中是有剪枝的议薪，最差也就是O（n!）尤蛮，n!表示n * (n-1) * .... * 1。
空間復(fù)雜度：O(n)斯议，和子集問題同理产捞。
解數(shù)獨(dú)問題分析：
時(shí)間復(fù)雜度：O(9^m) , m是'.'的數(shù)目。
空間復(fù)雜度：O(n^2)哼御，遞歸的深度是n^2
