代码随想录：回溯算法
回溯是递归的副产品，有递归过程就会有对应的回溯过程
回溯的本质是穷举，然后选出要的答案所以回溯法不高效，如果想让回溯法高效可以增加剪枝操作，但这样也改变不了回溯法穷举的本质
回溯算法可以解决的问题：
组合问题：按照一定规则在n个数中找到k个数的集合
切割问题：一个字符串按照一定规则切割有几种切割方式
子集问题：一个n个数的集合中有多少符合条件的子集
排列问题：n个数按照一定规则排列有几种排列方式
棋盘问题：n皇后，数独等问题
回溯法解决的问题都可以抽象成树结构，是一棵高度有限的N叉树
回溯三部曲：确定回溯函数中的返回值和参数，回溯法中返回值一般是void
确定回溯函数的终止条件，搜索到叶节点就存放答案结束本层递归
确定回溯搜索的遍历过程，使用一个for循环遍历集合区间，backtracking函数调用自己实现递归
for循环可以理解为横向遍历，递归纵向遍历，这样就遍历完整棵树，一般来讲遍历到叶子节点就是找到其中一个结果了
力扣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;
//当path数组大小达到k说明找到了一个集合，将他加入结果中
}
for (int i = start; i <= n; i++)
{
path.Add(i);
backtracking(n,k,i+1);
//递归，下一层start从i+1开始
path.RemoveAt(path.Count-1);
//回溯要把path数组也一同回溯
}
}
public IList<IList<int>> Combine(int n, int k)
{
backtracking(n,k,1);
return result;
}
}
上面的解法中有很多无效搜索，所以可以通过剪枝优化，将循环的部分中增加限制条件使不必要的循环不执行，for循环内条件改为
for (int i = start; i <= n-(k-path.Count)+1; i++)
//for循环开始执行的时候若后面可选择的数字数量少于需要的数量就可以不执行了，n-(k-path.Count)+1中+1是因为这个循环的选择包括起始位置
力扣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;
//回溯，同时回溯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();
//因为要对字符串做添加删除操作所以使用StringBuilder
void BackTracking(string dig,string[] map, int num)
{
if (num==dig.Length)
{
rsl.Add(temp.ToString());
return;
//终止条件，当前找到的数字的长度和要求的相同就输出
}
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);
//回溯时将temp也回溯
}
}
public IList<string> LetterCombinations(string digits)
{
string[] map = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
//建立映射，将每个数字对应的字母映射到对应数字上
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++){
//数组是排序的，因此只要下一层递归的第一个元素加进来就会超过目标值就可以不循环了
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);
//这种剪枝方法需要先进行排序
backtracking(candidates,target);
return result;
}
}
力扣40：组合总和II
public class Solution {
//和前面逻辑相同，只是多加了一个布尔值数组used来标记当前位置数字是否被使用过
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;
//剪枝的时候跳过不能只跳过一个重复数字，因此遇到需要跳过的数字时把这个数字的used值也设置成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)
{
//判断条件后面多打了；的话会直接进入循环，如果在rider写代码时候发现这个代码块后面的代码块是灰色的话大概率是这里多打了一个；
result.Add(new List<string>(path));
return;
//当切割线比字符串长度长说明已经找到了一组解，将他们加入结果中
}
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;
//不是回文串就直接下次循环
}
backtracking(s,i+1);
path.RemoveAt(path.Count-1);
//回溯时记得把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：复原IP地址
using System.Text;
思路和上题几乎相同，但是不以截断点判断是否结束而是以添加的.的数量判断
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());
//如果已经添加了三个.就判断剩余的部分是否符合要求，符合就是找到了一组解加入到结果中
}
return;
}
for (int i = start; i < s.Length; i++)
{
if (isValid(s,start,i))
{
s.Insert(i + 1, '.');
point++;
backtracking(s,i+2,point);
//加了.以后长度改变，下次递归的起点在添加的.的后面一位
point--;
s.Remove(i + 1, 1);
//回溯删除添加的.
}
else break;
//剪枝，如果这段不符合直接不用看后续了
}
}
bool isValid(StringBuilder s, int start, int end)
{
//判断是否符合要求，如果起点比终点还大肯定不行，以0开头还不是只有0也不行，不是0-9的数字不行，超过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));
//把添加结果放到放在终止条件上面，既可以做到第一次递归收集空集结果也可以防止后续漏掉元素
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标记元素是否未使用过以此来去重复
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);
//由于要求的集合中元素需要有序所以不能通过先排序的方法来去重复，因此使用hashset来标记本层已经使用过的数字，防止出现重复
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里的元素进行判断前要先判断是否为空，这里判断是否为空是看元素个数是不是0，而不能用path!=null这种语句
//如果当前元素不能放入path就直接下一个
}
used.Add(nums[i]);
//used内加入元素，在递归回溯的时候不删除就能够判断本层是否用过，因为used实在循环内定义的所以等循环进行到下一层时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标识起点
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和数组长度相同说明收集到一种排列
}
for (int i = 0; i < nums.Length; i++)
{
if (used[i])
{
continue;
//bool[] used初始化的值默认全为false，因此使用数字后将其改为true，当遇到对应位置值为true的数字就跳过
}
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
{
//在全排列的基础上要在每一层判断是否使用过相同的元素
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);
//判断当前元素是没使用过的才能进行回溯
}
}
}
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;
//行数为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();
//结果要求为IList<IList<string>>但是string不能进行修改因此在修改时使用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;
//判断右上是否冲突
}
}
//由于需要判断时该行下方的行还没有填入棋子所以不需要看左下右下正下
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实例化则需要new，否则在修改操作时对StringBuilder进行操作会同时修改所有的行
}
backtracking(n,0,board);
return result;
}
}
力扣37：解数独
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;
//遍历数组，找到.的位置开始填数字
}
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;
//如果九个数都不行就说明填错了，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;
//纵列有无重复
}
}
for (int i = 0; i < 9; i++)
{
if (board[row][i]==val)
{
return false;
//横行有无重复
}
}
int x = (row / 3)*3, y = (col / 3)*3;
//先除以3再乘以3就能找到他所在的那一块的第一个坐标值
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分开循环，否则只会看对角线
}
}
}
return true;
}
public void SolveSudoku(char[][] board)
{
backtracking(board);
}
}
