代碼隨想錄：回溯算法
回溯是遞歸的副產(chǎn)品，有遞歸過程就會有對應(yīng)的回溯過程
回溯的本質(zhì)是窮舉，然后選出要的答案所以回溯法不高效，如果想讓回溯法高效可以增加剪枝操作，但這樣也改變不了回溯法窮舉的本質(zhì)
回溯算法可以解決的問題：
????組合問題：按照一定規(guī)則在n個(gè)數(shù)中找到k個(gè)數(shù)的集合
????切割問題：一個(gè)字符串按照一定規(guī)則切割有幾種切割方式
????子集問題：一個(gè)n個(gè)數(shù)的集合中有多少符合條件的子集
????排列問題：n個(gè)數(shù)按照一定規(guī)則排列有幾種排列方式
????棋盤問題：n皇后，數(shù)獨(dú)等問題
回溯法解決的問題都可以抽象成樹結(jié)構(gòu)，是一棵高度有限的N叉樹
回溯三部曲：確定回溯函數(shù)中的返回值和參數(shù)，回溯法中返回值一般是void
確定回溯函數(shù)的終止條件，搜索到葉節(jié)點(diǎn)就存放答案結(jié)束本層遞歸
確定回溯搜索的遍歷過程，使用一個(gè)for循環(huán)遍歷集合區(qū)間，backtracking函數(shù)調(diào)用自己實(shí)現(xiàn)遞歸
for循環(huán)可以理解為橫向遍歷，遞歸縱向遍歷，這樣就遍歷完整棵樹，一般來講遍歷到葉子節(jié)點(diǎn)就是找到其中一個(gè)結(jié)果了
力扣77：組合
public?class?Solution?{
????IList<IList<int>>?result?=?new?List<IList<int>>();
????IList<int>?path?=?new?List<int>();
????void?backtracking(int?n,?int?k,?int?start)
????{
????????if?(path.Count==k)
????????{
????????????result.Add(new?List<int>(path));
????????????return;
//當(dāng)path數(shù)組大小達(dá)到k說明找到了一個(gè)集合，將他加入結(jié)果中
????????}
????????for?(int?i?=?start;?i?<=?n;?i++)
????????{
????????????path.Add(i);
????????????backtracking(n,k,i+1);
//遞歸，下一層start從i+1開始
????????????path.RemoveAt(path.Count-1);
//回溯要把path數(shù)組也一同回溯
????????}
????}
????public?IList<IList<int>>?Combine(int?n,?int?k)
????{
????????backtracking(n,k,1);
????????return?result;
????}
}
上面的解法中有很多無效搜索，所以可以通過剪枝優(yōu)化，將循環(huán)的部分中增加限制條件使不必要的循環(huán)不執(zhí)行，for循環(huán)內(nèi)條件改為
for?(int?i?=?start;?i?<=?n-(k-path.Count)+1;?i++)
//for循環(huán)開始執(zhí)行的時(shí)候若后面可選擇的數(shù)字?jǐn)?shù)量少于需要的數(shù)量就可以不執(zhí)行了，n-(k-path.Count)+1中+1是因?yàn)檫@個(gè)循環(huán)的選擇包括起始位置
力扣216：組合總和III
public?class?Solution?{
????IList<IList<int>>?result?=?new?List<IList<int>>();
????IList<int>?path?=?new?List<int>();
????void?backtracking(int?k,?int?sum,?int?start)
????{
????????if?(sum?<?0)
????????{
????????????return;
//剪枝
????????}
????????if?(path.Count==k)
????????{
????????????if?(sum==0)
????????????{
????????????????result.Add(new?List<int>(path));
????????????????return;
????????????}
????????????return;
//終止條件，不滿足條件的也要return
????????}
????????
????????for?(int?i?=?start;?i?<=?9-(k-path.Count)+1;?i++)
????????{
????????????path.Add(i);
????????????sum?-=?i;
????????????backtracking(k,sum,i+1);
????????????path.RemoveAt(path.Count-1);
????????????sum?+=?i;
//回溯，同時(shí)回溯sum和path
????????}
????}
????public?IList<IList<int>>?CombinationSum3(int?k,?int?n)
????{
????????backtracking(k,n,1);
????????return?result;
????}
}
力扣17：電話號碼的字母組合
public?class?Solution?{
????IList<string>?rsl?=?new?List<string>();
????StringBuilder?temp?=?new?StringBuilder();
//因?yàn)橐獙ψ址鎏砑觿h除操作所以使用StringBuilder
????void?BackTracking(string?dig,string[]?map,?int?num)
????{
????????if?(num==dig.Length)
????????{
????????????rsl.Add(temp.ToString());
????????????return;
//終止條件，當(dāng)前找到的數(shù)字的長度和要求的相同就輸出
????????}
????????string?str?=map[dig[num]-'0'];
????????for?(int?i?=?0;?i?<?str.Length;?i++)
????????{
????????????temp.Append(str[i]);
????????????BackTracking(dig,map,num+1);
????????????temp.Remove(temp.Length-1,1);
//回溯時(shí)將temp也回溯
????????}
????}
????public?IList<string>?LetterCombinations(string?digits)
????{
????????string[]?map?=?{?"",?"",?"abc",?"def",?"ghi",?"jkl",?"mno",?"pqrs",?"tuv",?"wxyz"?};
//建立映射，將每個(gè)數(shù)字對應(yīng)的字母映射到對應(yīng)數(shù)字上
????????if?(digits==null?||?digits.Length==0)
????????{
????????????return?rsl;
????????}
????????BackTracking(digits,map,0);
????????return?rsl;
????}
}
力扣39：組合總和
public?class?Solution?{
????IList<IList<int>>?result=new?List<IList<int>>();
????IList<int>?path=new?List<int>();
????void?backtracking(int[]candidates,int?sum){
????????if(sum<0){
????????????return;
//剪枝
????????}
????????if(sum==0){
????????????result.Add(new?List<int>(path));
????????????return;
????????}
????????for(int?i=0;i<candidates.Length&&?sum-candidates[i]>=0;i++){
//數(shù)組是排序的，因此只要下一層遞歸的第一個(gè)元素加進(jìn)來就會超過目標(biāo)值就可以不循環(huán)了
????????????path.Add(candidates[i]);
????????????sum-=candidates[i];
????????????backtracking(candidates[i..candidates.Length],sum);
????????????path.RemoveAt(path.Count-1);
????????????sum+=candidates[i];
//回溯記得全部回溯
????????}
????}
????public?IList<IList<int>>?CombinationSum(int[]?candidates,?int?target)?{
????????Array.Sort(candidates);
//這種剪枝方法需要先進(jìn)行排序
????????backtracking(candidates,target);
????????return?result;
????}
}
力扣40：組合總和II
public?class?Solution?{
//和前面邏輯相同，只是多加了一個(gè)布爾值數(shù)組used來標(biāo)記當(dāng)前位置數(shù)字是否被使用過
????IList<IList<int>>?result=new?List<IList<int>>();
????IList<int>?path=new?List<int>();
????void?backtracking(int[]candidates,int?sum,bool[]?used){
????????if(sum<0){
????????????return;
????????}
????????if(sum==0){
????????????result.Add(new?List<int>(path));
????????????return;
????????}
????????for(int?i=0;i<candidates.Length&&?sum-candidates[i]>=0;i++){
????????????if?(i>0&&?candidates[i]==candidates[i-1]&&?!used[i-1])
????????????{
????????????????used[i]=false;
//剪枝的時(shí)候跳過不能只跳過一個(gè)重復(fù)數(shù)字，因此遇到需要跳過的數(shù)字時(shí)把這個(gè)數(shù)字的used值也設(shè)置成false
????????????????continue;
????????????}
????????????path.Add(candidates[i]);
????????????sum-=candidates[i];
????????????used[i]?=?true;
????????????backtracking(candidates[(i+1)..candidates.Length],sum,used);
????????????path.RemoveAt(path.Count-1);
????????????sum+=candidates[i];
????????????used[i]?=?false;
????????}
????}
????public?IList<IList<int>>?CombinationSum2(int[]?candidates,?int?target)?{
????????Array.Sort(candidates);
????????bool[]?used?=?new?bool[candidates.Length];
????????backtracking(candidates,target,used);
????????return?result;
????}
}
力扣131：分割回文串
public?class?Solution
{
????private?IList<IList<string>>?result?=?new?List<IList<string>>();
????private?IList<string>?path?=?new?List<string>();
????public?IList<IList<string>>?Partition(string?s)?{
????????backtracking(s,0);
????????return?result;
????}
????void?backtracking(string?s,?int?start)
????{
????????if?(start?>=?s.Length)?
????????{
//判斷條件后面多打了；的話會直接進(jìn)入循環(huán)，如果在rider寫代碼時(shí)候發(fā)現(xiàn)這個(gè)代碼塊后面的代碼塊是灰色的話大概率是這里多打了一個(gè)；
????????????result.Add(new?List<string>(path));
????????????return;
//當(dāng)切割線比字符串長度長說明已經(jīng)找到了一組解，將他們加入結(jié)果中
????????}
????????for?(int?i?=?start;?i?<?s.Length;?i++)
????????{
????????????if?(isPalindrome(s,start,i))
????????????{
????????????????string?temp=s[start..(i+1)];
????????????????path.Add(temp);
//是回文串就把這一串加到path里
????????????}
????????????else
????????????{
????????????????continue;
//不是回文串就直接下次循環(huán)
????????????}
????????????backtracking(s,i+1);
????????????path.RemoveAt(path.Count-1);
//回溯時(shí)記得把path里面的東西刪掉再開始下次path的記錄
????????}
????}
????bool?isPalindrome(string?s,?int?start,?int?end)
????{
????????for?(int?i?=?start,j=end;?i<=j;?i++,j--)
????????{
????????????if?(s[i]!=s[j])
????????????{
????????????????return?false;
//判斷回文串
????????????}
????????}
????????return?true;
????}
}
力扣93：復(fù)原IP地址
using?System.Text;
思路和上題幾乎相同，但是不以截?cái)帱c(diǎn)判斷是否結(jié)束而是以添加的.的數(shù)量判斷
public?class?Solution
{
????private?IList<string>?result?=?new?List<string>();
????void?backtracking(StringBuilder?s,?int?start,int?point)
????{
????????if?(point==3)
????????{
????????????if?(isValid(s,start,s.Length-1))
????????????{
????????????????result.Add(s.ToString());
//如果已經(jīng)添加了三個(gè).就判斷剩余的部分是否符合要求，符合就是找到了一組解加入到結(jié)果中
????????????}
????????????return;
????????}
????????for?(int?i?=?start;?i?<?s.Length;?i++)
????????{
????????????if?(isValid(s,start,i))
????????????{
????????????????s.Insert(i?+?1,?'.');
????????????????point++;
????????????????backtracking(s,i+2,point);
//加了.以后長度改變，下次遞歸的起點(diǎn)在添加的.的后面一位
????????????????point--;
????????????????s.Remove(i?+?1,?1);
//回溯刪除添加的.
????????????}
????????????else?break;
//剪枝，如果這段不符合直接不用看后續(xù)了
????????}
????}
????bool?isValid(StringBuilder?s,?int?start,?int?end)
????{
//判斷是否符合要求，如果起點(diǎn)比終點(diǎn)還大肯定不行，以0開頭還不是只有0也不行，不是0-9的數(shù)字不行，超過255不行
????????if?(start>end)
????????{
????????????return?false;
????????}
????????if?(s[start]=='0'&&start!=end)
????????{
????????????return?false;
????????}
????????int?num?=?0;
????????for?(int?i?=?start;?i?<=?end;?i++)
????????{
????????????if?(s[i]>'9'||s[i]<'0')
????????????{
????????????????return?false;
????????????}
????????????num?=?num?*?10?+?s[i]?-?'0';
????????????if?(num>255)
????????????{
????????????????return?false;
????????????}
????????}
????????return?true;
????}
????public?IList<string>?RestoreIpAddresses(string?s)
????{
????????StringBuilder?ss?=?new?StringBuilder(s);
????????if?(s.Length>12)
????????{
????????????return?result;
//輸入的字符串超過12位就剪枝
????????}
????????backtracking(ss,0,0);
????????return?result;
????}
}
力扣78：子集
public?class?Solution
{
????private?IList<IList<int>>?result?=?new?List<IList<int>>();
????private?IList<int>?path?=?new?List<int>();
????void?backtracking(int[]?nums,?int?start)
????{
????????result.Add(new?List<int>(path));
//把添加結(jié)果放到放在終止條件上面，既可以做到第一次遞歸收集空集結(jié)果也可以防止后續(xù)漏掉元素
????????if?(start>=nums.Length)
????????{
????????????return;
????????}
????????for?(int?i?=?start;?i?<?nums.Length;?i++)
????????{
????????????path.Add(nums[i]);
????????????backtracking(nums,i+1);
????????????path.RemoveAt(path.Count-1);
????????}
????}
????public?IList<IList<int>>?Subsets(int[]?nums)?{
????????backtracking(nums,0);
????????return?result;
????}
}
力扣90：子集II
public?class?Solution
{
//和前面組合總和II一樣，先排序然后使用used標(biāo)記元素是否未使用過以此來去重復(fù)
????private?IList<IList<int>>?result?=?new?List<IList<int>>();
????private?IList<int>?path?=?new?List<int>();
????void?backtracking(int[]?nums,?int?start,bool[]?used)
????{
????????result.Add(new?List<int>(path));
????????if?(start>=nums.Length)
????????{
????????????return;
????????}
????????
????????for?(int?i?=?start;?i?<?nums.Length;?i++)
????????{
????????????if?(i>0&&?nums[i]==nums[i-1]&&?used[i-1]==false)
????????????{
????????????????used[i]?=?false;
????????????????continue;
????????????}
????????????path.Add(nums[i]);
????????????used[i]?=?true;
????????????backtracking(nums,i+1,used);
????????????path.RemoveAt(path.Count-1);
????????????used[i]?=?false;
????????}
????}
????public?IList<IList<int>>?SubsetsWithDup(int[]?nums)
????{
????????Array.Sort(nums);
????????bool[]?used=?new?bool[nums.Length];
????????backtracking(nums,0,used);
????????return?result;
????}
}
力扣491：遞增子序列
public?class?Solution
{
????private?IList<IList<int>>?result?=?new?List<IList<int>>();
????private?IList<int>?path?=?new?List<int>();
????void?backtracking(int[]?nums,?int?start)
????{
????????if?(path.Count>1)
????????{
????????????result.Add(new?List<int>(path));
????????}
????????HashSet<int>?used?=?new?HashSet<int>(201);
//由于要求的集合中元素需要有序所以不能通過先排序的方法來去重復(fù)，因此使用hashset來標(biāo)記本層已經(jīng)使用過的數(shù)字，防止出現(xiàn)重復(fù)
????????for?(int?i?=?start;?i?<?nums.Length;?i++)
????????{
????????????if?((path.Count!=0&&nums[i]<path.Last())||?(used.Count!=0&&used.Contains(nums[i])))
????????????{
????????????????continue;
//對path和used里的元素進(jìn)行判斷前要先判斷是否為空，這里判斷是否為空是看元素個(gè)數(shù)是不是0，而不能用path!=null這種語句
//如果當(dāng)前元素不能放入path就直接下一個(gè)
????????????}
????????????used.Add(nums[i]);
//used內(nèi)加入元素，在遞歸回溯的時(shí)候不刪除就能夠判斷本層是否用過，因?yàn)閡sed實(shí)在循環(huán)內(nèi)定義的所以等循環(huán)進(jìn)行到下一層時(shí)used會被重新定義所以不需要回溯
????????????path.Add(nums[i]);
????????????backtracking(nums,i+1);
????????????path.RemoveAt(path.Count-1);
????????}
????}
????public?IList<IList<int>>?FindSubsequences(int[]?nums)?{
????????backtracking(nums,0);
????????return?result;
????}
}
力扣46：全排列
public?class?Solution
{
//由于全排列中[1,2]和[2,1]是兩種不同的排列，因此不能用start標(biāo)識起點(diǎn)
????private?IList<IList<int>>?result?=?new?List<IList<int>>();
????private?IList<int>?path?=?new?List<int>();
????void?backtracking(int[]?nums,?bool[]?used)
????{
????????if?(path.Count==nums.Length)
????????{
????????????result.Add(new?List<int>(path));
????????????return;
//path和數(shù)組長度相同說明收集到一種排列
????????}
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????if?(used[i])
????????????{
????????????????continue;
//bool[] used初始化的值默認(rèn)全為false，因此使用數(shù)字后將其改為true，當(dāng)遇到對應(yīng)位置值為true的數(shù)字就跳過
????????????}
????????????used[i]?=?true;
????????????path.Add(nums[i]);
????????????backtracking(nums,used);
????????????used[i]?=?false;
????????????path.RemoveAt(path.Count-1);
????????}
????}
????public?IList<IList<int>>?Permute(int[]?nums)
????{
????????bool[]?used?=?new?bool[nums.Length];
????????backtracking(nums,used);
????????return?result;
????}
}
力扣47：全排列II
public?class?Solution
{
//在全排列的基礎(chǔ)上要在每一層判斷是否使用過相同的元素
????private?IList<IList<int>>?result?=?new?List<IList<int>>();
????private?IList<int>?path?=?new?List<int>();
????void?backtracking(int[]?nums,?bool[]?used)
????{
????????if?(path.Count==nums.Length)
????????{
????????????result.Add(new?List<int>(path));
????????????return;
????????}
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????if?(i>0&&?nums[i]==nums[i-1]&&?used[i-1]==false)
????????????{
????????????????continue;
//如果是一樣的元素就跳過
????????????}
????????????if?(used[i]==false)
????????????{
????????????????used[i]?=?true;
????????????????path.Add(nums[i]);
????????????????backtracking(nums,used);
????????????????used[i]?=?false;
????????????????path.RemoveAt(path.Count-1);
//判斷當(dāng)前元素是沒使用過的才能進(jìn)行回溯
????????????}
????????}
????}
????public?IList<IList<int>>?PermuteUnique(int[]?nums)?{
????????Array.Sort(nums);
//想判斷同樣的元素是否使用過就要先排序
????????bool[]?used?=?new?bool[nums.Length];
????????backtracking(nums,used);
????????return?result;
????}
}
力扣51：N皇后
using?System.Text;
public?class?Solution
{
????private?IList<IList<string>>?result?=?new?List<IList<string>>();
????IList<string>?board=new?List<string>();
????void?backtracking(int?n,int?row,?IList<string>?board)
????{
????????if?(row==n)
????????{
????????????
????????????result.Add(new?List<string>(board));
????????????return;
//行數(shù)為n則說明完成一組解
????????}
????????for?(int?col?=?0;?col?<?n;?col++)
????????{
????????????if?(isValid(row,col,board,n))
????????????{
????????????????StringBuilder?temp?=?new?StringBuilder(board[row]);
????????????????temp[col]?=?'Q';
????????????????board[row]?=?temp.ToString();
????????????????backtracking(n,row+1,board);
????????????????temp[col]?=?'.';
????????????????board[row]?=?temp.ToString();
//結(jié)果要求為IList<IList<string>>但是string不能進(jìn)行修改因此在修改時(shí)使用StringBuilder操作
????????????}
????????}
????}
????bool?isValid(int?row,?int?col,?IList<string>?board,?int?n)
????{
????????for?(int?i?=?0;?i?<?row;?i++)
????????{
????????????if?(board[i][col]=='Q')
????????????{
????????????????return?false;
//判斷相同縱列上方是否沖突
????????????}
????????}
????????for?(int?i=row-1,j=col-1;i>=0&&j>=0;i--,j--)
????????{
????????????if?(board[i][j]=='Q')
????????????{
????????????????return?false;
//判斷左上是否沖突
????????????}
????????}
????????for?(int?i=row-1,j=col+1;i>=0&&j<n;i--,j++)
????????{
????????????if?(board[i][j]=='Q')
????????????{
????????????????return?false;
//判斷右上是否沖突
????????????}
????????}
//由于需要判斷時(shí)該行下方的行還沒有填入棋子所以不需要看左下右下正下
????????return?true;
????}
????public?IList<IList<string>>?SolveNQueens(int?n)
????{
????????StringBuilder?s?=?new?StringBuilder();
????????for?(int?i?=?0;?i?<?n;?i++)
????????{
????????????s.Append('.');
????????}
????????for?(int?i?=?0;?i?<?n;?i++)
????????{
????????????board.Add(s.ToString());
如果使用StringBuilder實(shí)例化則需要new，否則在修改操作時(shí)對StringBuilder進(jìn)行操作會同時(shí)修改所有的行
????????}
????????backtracking(n,0,board);
????????return?result;
????}
}
力扣37：解數(shù)獨(dú)
public?class?Solution?{
????bool?backtracking(char[][]?board)
????{
????????for?(int?i?=?0;?i?<?9;?i++)
????????{
????????????for?(int?j?=?0;?j?<?9;?j++)
????????????{
????????????????if?(board[i][j]!='.')
????????????????{
????????????????????continue;
//遍歷數(shù)組，找到.的位置開始填數(shù)字
????????????????}
????????????????for?(char?k?=?'1';?k<='9';k++)
????????????????{
????????????????????if?(isValid(i,j,board,k))
????????????????????{
????????????????????????board[i][j]?=?k;
????????????????????????if?(backtracking(board))
????????????????????????{
????????????????????????????return?true;
????????????????????????}
????????????????????????board[i][j]?=?'.';
????????????????????}
????????????????}
????????????????return?false;
//如果九個(gè)數(shù)都不行就說明填錯(cuò)了，return false
????????????}
????????}
????????return?true;
????}
????bool?isValid(int?row,?int?col,?char[][]?board,?int?val)
????{
????????for?(int?i?=?0;?i?<?9;?i++)
????????{
????????????if?(board[i][col]==val)
????????????{
????????????????return?false;
//縱列有無重復(fù)
????????????}
????????}
????????for?(int?i?=?0;?i?<?9;?i++)
????????{
????????????if?(board[row][i]==val)
????????????{
????????????????return?false;
//橫行有無重復(fù)
????????????}
????????}
????????int?x?=?(row?/?3)*3,?y?=?(col?/?3)*3;
//先除以3再乘以3就能找到他所在的那一塊的第一個(gè)坐標(biāo)值
????????for?(int?i?=?x;?i?<?x+3;?i++)
????????{
????????????for?(int?j?=?y;?j?<?y+3;?j++)
????????????{
????????????????if?(board[i][j]==val)
????????????????{
????????????????????return?false;
//x和y分開循環(huán)，否則只會看對角線
????????????????}
????????????}
????????}
????????return?true;
????}
????public?void?SolveSudoku(char[][]?board)
????{
????????backtracking(board);
????}
}
