回溯法解决的问题

回溯法模板

1. 返回值一般为void
2. 参数先写逻辑用到啥参数再填啥参数
3. 终止条件到达叶子节点保存当前结果返回
4. 遍历过程回溯法一般在集合中递归搜索集合的大小构成了树的宽度递归的深度构成了树的深度
    
   如图
   横向中for遍历集合区间有几个子集合for循环就执行多少次
   纵向中backtracking自己调用自己实现递归多少层递归树的深度就是多少
   
5. 回溯算法的模板框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择本层集合中元素树中节点孩子的数量就是集合的大小) {
        处理节点;
        backtracking(路径选择列表); // 递归
        回溯撤销处理结果
    }
}

组合问题

1. 组合

77.组合
给定两个整数 n 和 k返回 1 … n 中所有可能的 k 个数的组合。

递归树

• 最开始集合为1,2,3,4从左向右取数取过的数不再重复
• 第一次取1集合变为2,3,4因为k为2只需再取一个数就行分别取2,3,4得到集合[1,2][1,3][1,4]以此类推
• 每次从集合中选取元素可选择的范围随着选择的进行而收缩调整可选择的范围
  
  画递归树是解决回溯问题最重要的步骤

回溯法三部曲

1. 递归函数参数
   两个全局变量一个用来存放符合条件单一结果一个用来存放符合条件结果的集合

List<Integer>path=new ArrayList<>();//某次结果
List<List<Integer>>res=new ArrayList<>();//所有结果

函数里一定有n和k两个参数另外还需要一个参数 index用来记录本层递归中集合从哪里开始遍历集合即[1,…,n]。
index就是为了防止重复的组合需要其记录下一层递归搜索的起始位置。

因此递归函数参数如下public void backtracking(int n,int k,int start)

2. 终止条件
   如果path数组大小达到k说明找到了一个子集大小为k的组合了图中path存的就是根节点到叶子节点的路径如图红色部分
   
   此时用res数组保存path然后return。
   所以终止条件代码如下

if(path.size()==k){
	  res.add(new ArrayList<>(path));
	  return;
	}

3. 单层搜索过程
   for循环横向遍历递归纵向遍历代码如下

for(int i=index;i<=n;i++){
      path.add(i);
      backtrack(n,k,i+1);//递归下一层搜索从i+1开始
      path.remove(path.size()-1);//回溯撤销处理的节点
    }

剪枝优化

仔细看遍历过程代码其中遍历范围是可以剪枝优化的

for(int i=index;i<=n;i++){
      path.add(i);
      backtrack(n,k,i+1);//递归下一层搜索从i+1开始
      path.remove(path.size()-1);//回溯撤销处理的节点
    }

举例n=4k=4第一层for循环时从元素2开始子集大小肯定达不到4因此之后都没有意义了。在第二层for循环从元素3开始的遍历都没有意义了。

所以如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了那么就没有必要搜索了

优化过程如下

1. 已经选择的元素个数path.size()
2. 还需要的元素个数k-path.size()
3. 集合中至多要从该起始位置n-(k-path.size())+1开始遍历
   由于起始位置是从1开始的因此起始位置要+1举个例子就可以知道了

因此剪枝优化后的for循环如下

for(int i=index;i<=n-(k-path.size())+1;i++)

2. 组合总和III

216. 组合总和 III
找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数并且每种组合中不存在重复的数字。

说明

• 所有数字都是正整数。
• 解集不能包含重复的组合。

递归树

相比于77.组合多了一个和为n的限制并且整个集合是固定的[1,…,9]而上一题集合为非固定的[1,…,n]

递归树如下

回溯三部曲

1. 递归函数参数
   类似上一题 组合同样需要path存放单次结果和res存放全部结果
   除此之外递归函数参数中k和index必然存在还需要记录目标和的targetSum以及记录path中元素总和的sum。
   所以参数如下

List<Integer>path=new ArrayList<>();
List<List<Integer>>res=new ArrayList<>();
public void dfs(int k,int index,int targetSum,int sum)

2. 终止条件
   依据题意path元素数目达到k && sum==targetSum时终止递归

3. 单层搜索过程
   和上一题77.组合的区别有二
   一是集合固定为[1,…,9]因此for循环固定i<=9
   二是需要sum来统计path中元素总和。

代码如下

	for(int i=index;i<=9;i++){
	    path.add(i);
	    sum+=i;
	    dfs(n,k,i+1,sum);
	    sum-=i;
	    path.remove(path.size()-1);
	}

剪枝优化

两部分可以剪枝

1. 同77.组合for循环的范围可以进行剪枝i<9-(k-path.size())+1或者直接当path.size()>k时返回
2. sum已经大于n时往后遍历没有意义直接剪掉如下图所示
   

剪枝后代码

for(int i=index;i<=9-(k-path.size())+1;i++){
    if(sum<=n){
        path.add(i);
        sum+=i;
        dfs(n,k,i+1,sum);
        sum-=i;
        path.remove(path.size()-1);
    }
}

3. 电话号码的数字总和

17. 电话号码的字母组合
给定一个仅包含数字 2-9 的字符串返回所有它能表示的字母组合。
给出数字到字母的映射如下与电话按键相同。注意 1 不对应任何字母。

递归树

回溯三部曲

1. 递归函数参数
   类似上一题 组合同样需要path存放单次结果和res存放全部结果
   除此之外递归函数参数中digits必然存在另外还有int型的index参数。
   需要注意的是这里index的含义和77.组合以及216. 组合总和 III中表示起始位置的index不同这里的index记录的是遍历的第几个数字就是用来遍历digits的。
   所以参数如下

StringBuffer path=new StringBuffer();
List<List<Integer>>res=new ArrayList<>();
public void dfs(String digits,int index)

2. 终止条件
   依据题意index==digits.length() 时终止递归

3. 单层搜索过程

int num=digits.charAt(index)-'0';
String value=strs[num-2];//数字对应的字符集
for(int i=0;i<value.length();i++){
    sb.append(value.charAt(i));
    dfs(digits,index+1);//处理digits的下一个位置
    sb.deleteCharAt(sb.length()-1);
}

4. 组合总和

39. 组合总和
给定一个无重复元素的数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的数字可以无限制重复被选取。
说明
所有数字包括 target都是正整数。
解集不能包含重复的组合。

递归树

回溯三部曲

1. 递归函数参数
   path和res全局变量是固定套路
   递归函数中集合candidates和目标值target必存在除此之外还需要sum来记录path中元素总和 以及 startIndex来控制for循环起始位置
    
   这里衍生出的一个重要问题是对于组合问题什么时候需要 startIndex 作为循环开始位置呢
   如果是一个集合求组合就需要startIndex如77.组合216.组合总和III
   如果是多个集合取组合各个集合之间互不影响就不用startIndex如17.电话号码的字母组合
   注意以上仅针对组合问题排列问题是另一个分析方法。
2. 递归终止条件
   sum==target时收集结果并返回
3. 单层搜索过程

for(int i=index;i<n;i++){
    if(sum<target){//剪枝
        path.add(candidates[i]);
        dfs(candidates,target,i,sum+candidates[i]);//关键点不需要i+1表示可以重复读取当前元素
        path.remove(path.size()-1);
    }
}

总结

这题和之前的77.组合、216. 组合总和 III有两点不同

• 组合没有数量要求77和216都要求k个数的组合
• 元素可无限重复选取77和216都要求无重复数字

对于组合问题啥时候用startIndex啥时候不用做了总结主要对比17. 电话号码的字母组合题

5. 组合总和II

40.组合总和II
给定一个数组 candidates 和一个目标数 target 找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用一次。
说明 所有数字包括目标数都是正整数。解集不能包含重复的组合。

递归树

这题和上一题39. 组合总和的主要区别如下

1. 39题集合中有重复数字而本题集合中无重复数字
2. 39题集合中数字可以无限次使用而本题每个数字只能使用一次

本题难点在于有重复数字但是还不能有重复组合

回溯三部曲

1. 递归函数参数

List<Integer>path=new ArrayList<>();
List<List<Integer>>res=new ArrayList<>();
public void dfs(int[] candidates,int target,int index,int sum){

• 递归终止条件
  sum==target 时收集结果并返回

• 单层搜索过程
  需要额外注意的就是去重这里“位于同一树层”&&“两元素相同”则跳过

for(int i=index;i<n;i++){
	//对同一树层使用过的元素进行跳过
    if(i>index&&candidates[i]==candidates[i-1])
        continue;
    if(sum<target){//剪枝
        path.add(candidates[i]);
        dfs(candidates,target,i+1,sum+candidates[i]);
        path.remove(path.size()-1);
    }
}

切割问题

切割问题类似于组合问题例如对于字符串abcdef

• 组合问题选取一个a之后在bcdef中再去选取第二个选取b之后在cdef中再选取第三个…。
• 切割问题切割一个a之后在bcdef中再去切割第二段切割b之后在cdef中再切割第三段…。

1. 分割字符串

131.分割回文串
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

递归树

看递归树可以发现切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。

回溯三部曲

1. 递归函数参数
   切割过的地方不能重复切割因此需要startIndex参数和组合问题保持一致

List<String>path=new ArrayList<>();
List<List<String>>res=new ArrayList<>();
public void dfs(String s,int startIndex)

2. 递归终止条件
   index>=s.length() 时收集结果并返回
3. 单层搜索过程

for(int i=index;i<n;i++){
	//index到i是回文串切割
    if(isPalindrome(s,index,i)){
        String str=s.substring(index,i+1);
        path.add(str);
        dfs(s,i+1);//不能重复切割因此传入i+1
        path.remove(path.size()-1);
    }
}

那么如何判断字符串是回文串呢
可以使用双指针法一个指针从前向后另一个指针从后向前如果前后指针所指向的元素都是相等的就是回文字符串了。

public boolean isPalindrome(String s,int start,int end){
    for(int i=start,j=end;i<j;i++,j--){
        if(s.charAt(i)!=s.charAt(j))
            return false;
    }
    return true;
}

优化

优化的思路是如何更高效的计算一个字符串是否是回文串
对于字符串s给定起始下标和终止下标判断截取出的字符串是否为回文串其中一定有重复计算存在
例如给定“abcde”在已知“bcd”不是回文串的情况下不需要双指针判断“abcde”而可以直接判定它一定不是回文串。

具体来说给定一个字符串s长度为n它成为回文串的充要条件是s[0]==s[n-1]且s[1,…,n-2]是回文串。因此使用动态规划的方法对回文串判断进行改进。
对于动态规划的方法先一次性计算出对于字符串s它的任何子串是否是回文串然后在回溯函数中直接查询即可省去了双指针移动判断这一步骤。

代码如下

//动态规划计算s的各个子串是否是回文串
f=new boolean[n][n];
for(int i=n-1;i>=0;i--){
    //需要倒序判断保证第i行时第i+1行已经计算好了
    for(int j=i;j<n;j++){
        char t1=s.charAt(i),t2=s.charAt(j);
        if(i==j)
            f[i][j]=true;
        //相邻字符串                    
        else if(j-i==1)
            f[i][j]=(t1==t2);
        else
            f[i][j]=(t1==t2&&f[i+1][j-1]);
    }
}

//回溯过程
for(int i=index;i<n;i++){
    if(f[index][i]){
        String str=s.substring(index,i+1);
        path.add(str);
        dfs(s,i+1);
        path.remove(path.size()-1);
    }
}

总结

总结一下本题的难点

• 如何模拟切割线
• 切割问题中递归如何终止
• 在递归循环中如何截取子串
• 如何判断回文

2. 复原IP地址

93.复原IP地址
给定一个字符串 s将 s 分割成一些子串使每个子串都是回文串。
返回 s 所有可能的分割方案。
示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

递归树

回溯三部曲

1. 递归函数参数
   由于不能重复分割因此index一定是需要的记录下一层递归分割的开始位置
   对于本题还需要一个变量 pointNum 记录IP地址中加逗号的数量。
   所以代码如下

List<String>res=new ArrayList<>();
public void dfs(String s,int index,int poinNum)

2. 递归终止条件
   由于涉及IP地址而不是简单的切割因此与131.分割回文串还不一样
   本题明确要求分成4段所以不能用切割线切到最后作为终止条件
   pointNum表示逗号数量因此当pointNum为3时说明字符串分为4段了如果此时第四段合法则加入结果集中
   代码如下

if(pointNum==3){
   注意这里一定要用s.length()而不能用n因为s要加分割符长度会变
   if(isValid(s,index,s.length()-1))
       res.add(s);
   return;
}

3. 单层搜索过程

• 截取子串
  切割后的字符串如果合法就在后面加上“.”
  如果不合法则结束本层循环
• 递归和回溯过程
  递归调用时下一层递归开始的index要从 i+2 开始因为在字符串中添加了“.”同时记录分隔符数目的pointNum要+1
  回溯的时候将添加的“.”删掉并且pointNum要-1

for(int i=index;i<s.length();i++){
    if(isValid(s,index,i)){
        s=s.substring(0,i+1)+"."+s.substring(i+1);//添加.
        dfs(s,i+2,pointNum+1);
        s=s.substring(0,i+1)+s.substring(i+2);//删掉.
    }
    else
        break;//不合法直接结束本层循环
}

判断子串是否合法

主要考虑如下三点

1. 段位以0开头不合法
2. 段位含有非正整数字符不合法
3. 段位大于255不合法

isValid函数代码如下

//判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法
public boolean isValid(String s,int start,int end){
    if(start>end)
        return false;
    //以0开头
    if(s.charAt(start)=='0'&&start!=end)
        return false;
    int num=0;
    for(int i=start;i<=end;i++){
        char ch=s.charAt(i);
        //含非正整数字符
        if(ch<'0'||ch>'9')
            return false;
        //大于255
        num=num*10+(ch-'0');
        if(num>255)
            return false;
    }
    return true;
}

子集问题

1. 子集

78.子集
给定一组不含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。你可以按 任意顺序 返回解集。

示例: 输入: “aab” 输出: [ [“aa”,“b”], [“a”,“a”,“b”] ]

递归树

如果把子集问题、组合问题、分割问题都抽象成一棵树的话那么组合问题和分割问题都是收集树的叶子节点而子集问题是找树的所有节点

子集也是一种组合问题因为它的集合是无序的子集{1,2}和{2,1}是一样的

那么既然是无序的取过的元素不会重复取写回溯算法的时候for就要从startIndex开始而不是从0开始

求子集问题抽象成递归树如下

从图中红线部分可以看出遍历这个树的时候把所有节点都记录下来就是要求的子集集合。

回溯三部曲

1. 递归函数参数
   常规参数单次结果path全部结果res数组nums递归开始位置startIndex。

2. 递归终止条件
   从递归树中可以看出剩余集合为空的时候就是叶子节点。
   那么什么时候剩余集合为空呢
   就是startIndex > 数组长度的时候终止。
   但其实可以不用加终止条件因为startIndex>=nums.length本层for循环本来也结束了。

3. 单层搜索过程
   求取子集问题不需要任何剪枝因为子集就是要遍历整棵树

for(int i=index;i<n;i++){
    path.add(nums[i]);
    dfs(nums,i+1);
    path.remove(path.size()-1);
}

跟上述组合、切割问题比起来子集问题还是蛮简单的

2. 子集II

90.子集II
给定一个可能包含重复元素的整数数组 nums返回该数组所有可能的子集幂集。
说明解集不能包含重复的子集。

示例:
输入: [1,2,2]
输出: [ [2], [1], [1,2,2], [2,2], [1,2], [] ]

递归树

子集+去重的一道题

子集可以参考上一题去重参考40.组合总和II

本题过于简单甚至没有回溯三部曲代码如下

class Solution {
    int n;
    List<Integer>path=new ArrayList<>();
    List<List<Integer>>res=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        n=nums.length;
        Arrays.sort(nums);
        dfs(nums,0);
        return res;
    }
    public void dfs(int[] nums,int index){
        res.add(new ArrayList<>(path));

        for(int i=index;i<n;i++){
            if(i>index&&nums[i]==nums[i-1])
                continue;
            path.add(nums[i]);
            dfs(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

3. 递增子序列

491.递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列递增子序列的长度至少是2。

示例:
输入: [4, 6, 7, 7]
输出: [[4, 6], [4, 7], [4, 6, 7], [4, 6, 7, 7], [6, 7], [6, 7, 7], [7,7], [4,7,7]]

说明:
给定数组的长度不会超过15。
数组中的整数范围是 [-100,100]。
给定数组中可能包含重复数字相等的数字应该被视为递增的一种情况。

递归树

本题递增子序列类似取有序的子集且不能有重复的子序列出现即需要去重
但是本题要求的是递增子序列是不能对原数组进行排序的因此不能使用之前的去重逻辑
原有去重逻辑先sort再剔除nums[i]==nums[i-1]的

回溯三部曲

1. 递归函数参数

List<Integer>path=new ArrayList<>();
List<List<Integer>>res=new ArrayList<>();
public void dfs(int[] nums,int index)

2. 递归终止条件

//注意这里不要return因为要返回树上所有节点
if(path.size()>=2){
    res.add(new ArrayList<>(path));
}

3. 单层搜索过程
   从递归树中可以看出同一父节点下的同层使用过的元素就不能再使用了
   
   本题去重方法利用used数组同层遍历过的数组元素used=1否则为0

int[] used=new int[201];
for(int i=index;i<n;i++){
    //非递增 或者 同层已经遍历过了跳过
    if((!path.isEmpty()&&nums[i]<path.get(path.size()-1))||used[nums[i]+100]==1)
        continue;
    
    path.add(nums[i]);
    used[nums[i]+100]=1;//加100是为了避免下标出现负数nums值最小为-100
    dfs(nums,i+1);
    path.remove(path.size()-1);
}

排列问题

1. 全排列

46.全排列
给定一个 没有重复 数字的序列返回其所有可能的全排列。

示例:
输入: [1,2,3]
输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

递归树

回溯三部曲

首先排列是有序的{1,2} 和 {2,1} 是两个不同的排列这是和子集以及组合问题不同的地方。

1. 递归函数参数
   排列问题需要used数组标记已经选择的元素

boolean[] used;//记录数组中每个元素是否被使用过
List<Integer>path=new ArrayList<>();
List<List<Integer>>res=new ArrayList<>();
public void dfs(int[] nums)

2. 递归终止条件
   观察递归树什么时候到达叶子节点呢path中元素个数==nums.length时

if(path.size()==n){
    res.add(new ArrayList<>(path));
    return;
}

3. 单层搜索过程
   排列问题每次都要从头开始搜索例如元素1已经在{1,2}中用过了但是还要在{2,1}中再用一次。
   因此需要used数组记录当前path中哪些元素使用过了一个排列里一个元素只能使用一次。

for(int i=0;i<n;i++){
   if(!used[i]){
       path.add(nums[i]);
       used[i]=true;
       dfs(nums);
       used[i]=false;
       path.remove(path.size()-1);
   }
}

总结

此时应该能感受到排列问题的不同

1. 每层都是从0开始而不是startIndex
2. 需要used数组记录path里都放了哪些元素

2. 全排列II

47.全排列 II
给定一个可包含重复数字的序列 nums 按任意顺序 返回所有不重复的全排列。

示例
输入nums = [1,1,2]
输出 [[1,1,2], [1,2,1], [2,1,1]]

递归树

这道题目和46.全排列的区别在与给定一个可包含重复数字的序列要返回所有不重复的全排列。

这里又涉及到去重了。

去重一定要对元素进行排序这样才方便通过相邻节点判断是否重复使用了。

图中我们对同一树层前一位如果使用过那么就进行去重。

一般来说

• 组合、排列问题叶子节点上收集结果
• 子集问题取树上所有节点的结果。

回溯三部曲

public void dfs(int[] nums){
	//递归终止条件
    if(path.size()==n){
        res.add(new ArrayList<>(path));
        return;
    }
    for(int i=0;i<n;i++){
    	//used[i-1] == true说明同一树枝nums[i-1]使用过
    	//used[i-1] == false说明同一树层nums[i-1]使用过
    	//如果同一树层nums[i-1]使用过则直接跳过
        if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
            continue;
        if(!used[i]){
            path.add(nums[i]);
            used[i]=true;
            dfs(nums);
            used[i]=false;
            path.remove(path.size()-1);
        }
    }
}

拓展

去重最关键的部分

if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false)
	continue;

如果改成used[i]==true也是正确的

if(i>0&&nums[i]==nums[i-1]&&used[i-1]==true)
	continue;

这是为什么呢

used[i-1] == false树层前一位去重
used[i-1] == true树枝前一位去重

用[1,1,1]举个例子
树层上去重used[i-1] == false的树形结构如下

树枝上去重used[i-1] == true的树形结构如下

树层上对前一位去重非常彻底效率很高树枝上对前一位去重虽然可以得到最后的答案但做了很多无用的搜索。

棋盘问题

N皇后

51. N 皇后
按照国际象棋的规则皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将n个皇后放置在n×n的棋盘上并且使皇后彼此之间不能相互攻击。

给你一个整数n 返回所有不同的n皇后问题的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。

递归树

首先确定n皇后问题的约束条件

1. 不能同行
2. 不能同列
3. 不能同斜线

然后去看看怎么确定皇后的位置可以抽象为一棵树。

从图中可以看出二维矩阵的高度就是这棵树的高度矩阵的宽就是树形结构中每一个节点的宽度。

我们用皇后的约束条件来回溯搜索这棵树只要搜索到了树的叶子节点说明就找到了皇后们的合理位置。

回溯三部曲

1. 递归函数参数
   n是矩阵的行列数row记录当前遍历到棋盘的第几层了。

List<List<String>>res=new ArrayList<>();
public void dfs(int n,int row,char[][] chessboard)

2. 递归终止条件
   递归到叶子节点棋盘到底了即row==n时收集结果并返回。

if(row==n){
   res.add(Array2List(chessboard));
   return;
}

//char[][]转List
public List Array2List(char[][] chessboard){
    List<String>list=new ArrayList<>();
    for(char[] c:chessboard){
        list.add(String.copyValueOf(c));
    }
    return list;
}

3. 单层搜索过程
   row控制棋盘的行也就是递归深度col控制棋盘的列确定皇后的放置位置。
   每一行都是从第0列开始搜因此col都是从0开始。

for(int col=0;col<n;col++){
    if(isValid(row,col,n,chessboard)){//位置合法才可以放
        chessboard[row][col]='Q';//放置皇后
        dfs(n,row+1,chessboard);
        chessboard[row][col]='.';//撤回皇后
    }
}

• 验证棋盘是否合法
  按照棋盘的三个约束条件不能同行同列同斜线45度和135度进行去重。
  如果左斜上方已经放置了皇后则该位置不合法不能再放置皇后。

public boolean isValid(int row,int col,int n,char[][] chessboard){
	//同列无皇后
	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<n;i--,j++){
	    if(chessboard[i][j]=='Q')
	        return false;
	}
	//左斜上无皇后
	for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
	    if(chessboard[i][j]=='Q')
	        return false;
	}
	return true;
}

解数独

37. 解数独
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图
数独部分空格内已填入了数字空白格用 ‘.’ 表示。

提示

• 给定的数独序列只包含数字 1-9 和字符 ‘.’ 。
• 你可以假设给定的数独只有唯一解。
• 给定数独永远是 9x9 形式的。

递归树

本题要做的是二维递归

N皇后问题是因为每行每列只放一个皇后只需要一层for循环遍历一行递归来遍历列然后一行一列确定皇后的唯一位置。

本题就不一样了棋盘中的每一个位置都需要放置一个数字N皇后一行只放一个皇后并检查数字是否合法解数独的递归树比N皇后问题更深更宽。

回溯三部曲

1. 递归函数以及参数
   递归函数的返回值是boolean型
   因为解数独找到一个符合条件立即返回相当于找从根节点到叶子节点一条唯一路径所以需要boolean返回值。

public boolean dfs(char[][] board)

2. 递归终止条件
   不需要递归终止条件
   因为解数独是要遍历整个递归树找到可能的叶子节点就立刻返回。
   递归的下一层棋盘一定比上一层多一个数等数填满了自然就终止了所以不需要终止条件

3. 单层搜索过程
   由递归树中可以看出我们需要一个二维的递归两个for循环嵌套着递归
   一个for循环遍历棋盘的行一个for循环遍历棋盘的列一行一列确定下来之后递归遍历这个位置放9个数字的可能性

public boolean dfs(char[][] board){
    for(int i=0;i<board.length;i++){
        for(int j=0;j<board[0].length;j++){
            if(board[i][j]!='.')
                continue;
            //board[i][j]放k是否合适
            for(char k='1';k<='9';k++){
                if(isValid(i,j,k,board)){
                    board[i][j]=k;
                    if(dfs(board))  return true;//找到一组合适的立刻返回
                    board[i][j]='.';
                }
            }
            return false;//9个数都不合适返回
        }
    }
    return true;//遍历完没有返回false说明找到了合适棋盘位置了
}

注意这里return false
如果一行一列确定下来了尝试了9个数都不行说明这个棋盘找不到解决数独问题的解。
那么就会直接返回所以即使没有终止条件也不会由于填不满棋盘而无限递归下去。

• 判断棋盘是否合法
  判断合法的三个维度同行、同列、9宫格内是否重复
  除此之外第 i 行第 j 列的格子位于( ⌊i/3⌋, ⌊j/3⌋ )个九宫格中注意一下这里下标的计算。

public boolean isValid(int row,int col,char val,char[][] board){
    //检查行重复
    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 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;
}

总结

性能分析

问题类型	时间复杂度	空间复杂度	备注
子集	$O(n\times 2^n)$	O(n)	每个元素取或者不取->$2^n$构造每一组子集填进数组->n
排列	$O(n!)$	O(n)
组合	$O(n\times 2^n)$	O(n)	组合问题其实就是一种子集问题最坏情况也不会超过子集的时间复杂度
N皇后	$O(n!)$	O(n)	皇后之间不能见面有剪枝所以最差就是$O(n!)$
解数独	$O(9^m)$	$O(n^2)$	m是‘.’的数目递归深度是$n^2$

几个问题

复习回溯的时候可以考虑如下几个问题

1. 如何理解回溯法的搜素过程
2. 如何去重如何理解“树枝去重”和“树层去重”
3. 去重的几种方法
4. 如何理解二维递归

以上均参考自代码随想录-回溯算法。

p.s 历时9天终于把回溯法学完了
起初只是因为组合问题又忘了一气之下决定好好总结一下回溯算法这么多天下来对于回溯算法的分析方法有了更深程度的掌握确实获益匪浅