回溯算法
一、理论知识
1.什么是回溯算法？
回溯法也可以叫做回溯搜索法，它是一种搜索的方式。
回溯是递归的副产品，只要有递归就会有回溯。回溯函数就是递归函数，二者指的是同一个函数。
2.回溯的应用
回溯法一般可以解决如下几种问题：
- 组合问题：N个数里面按一定规则找出k个数的集合；
- 切割问题：一个字符串按一定规则有几种切割方式；
- 子集问题：一个N个数的集合里有多少符合条件的子集；
- 排列问题：N个数按一定规则全排列，有几种排列方式；
- 棋盘问题：N皇后，解数独等等。
3.将回溯抽象为N叉树
回溯法解决的问题都可以抽象为树形结构。
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以回溯抽象出来的必然是一棵高度有限的N叉树。
因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。
递归就要有终止条件，所以回溯抽象出来的必然是一棵高度有限的N叉树。
4.回溯模板
-
回溯函数返回值和参数
回溯函数返回值一般为void。
因为回溯算法需要的参数不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。
-
回溯终止条件
回溯什么时候到达了终止条件？
——因为回溯都可以抽象成N叉树，所以一般来说搜到叶子节点了，也就找到了满足条件的一条答案，此时就到达了终止条件，把这个答案存放起来，并结束本层递归。
-
回溯单层逻辑——即搜索过程
回溯搜索的过程分为横向搜索(for循环)和纵向搜索(递归)。 -
回溯整体模板
二、相关题目推荐
1. 组合问题
（1）77. 组合
-
思路：以n=4，k=2为例(即从1，2，3，4中找出所有2个数的组合)，将回溯过程抽象成树型结构(如下)。
可以看出，这棵树一开始集合是 1，2，3，4， 从左向右取数，取过的数不再重复取。第一层第一次取走1，集合变为2，3，4 ，来到第二层第一个节点。因为k为2(终止条件)，我们只需要再取一个数就可以了，分别取2，3，4，得到集合[1,2] [1,3] [1,4]，此时要回溯到第一层，再取走2，集合变成3，4...以此类推。
因此每次搜索到叶子节点，我们就得到了一个结果。所以终止条件就是到达叶子节点的时候终止，相当于只需要把达到叶子节点的结果收集起来，就可以求得 n个数中k个数的组合集合。
★为什么需要startIdx参数？
从下图中红线部分可以看出，在集合[1,2,3,4]取1之后，下一层递归，就要在[2,3,4]中取数了，那么下一层递归如何知道从[2,3,4]中取数呢，靠的就是startIndex。因此需要startIndex来记录下一层递归搜索的起始位置。
class Solution { List<List<Integer>> rslt=new ArrayList<List<Integer>>(); //收集k个数的组合 List<Integer> path=new ArrayList<Integer>(); public List<List<Integer>> combine(int n, int k) { backtracking(n,k,1); return rslt; } public void backtracking(int n,int k,int startIdx) { //终止条件——收集结果 if(path.size()==k){ //★注意不要直接add(path)！ rslt.add(new ArrayList<>(path)); return; } //递归逻辑——遍历的过程 //横向遍历 for(int i=startIdx;i<=n;i++){ path.add(i); //纵向遍历 backtracking(n,k,i+1); //★回溯 path.remove(path.size()-1); } } }★优化：以n=4，k=4为例：第一层for循环的时候，取走1后，从元素2开始的遍历都没有意义了；在第二层for循环，取走2后，从元素3开始的遍历都没有意义了。
因此如果for循环选择的起始位置之后的元素个数 小于 我们需要的元素个数了，那么就没有必要继续搜索了。
优化过程如下(想不通就举个数试试)：
-
已经选择的元素个数：path.size();
-
还需要的元素个数: k - path.size();
-
列表中剩余元素(n-i) >= 还需要的元素个数（k - path.size()）
-
for循环终止条件 : i <= n - (k - path.size()) + 1
class Solution { List<List<Integer>> rslt=new ArrayList<List<Integer>>(); //收集k个数的组合 List<Integer> path=new ArrayList<Integer>(); public List<List<Integer>> combine(int n, int k) { backtracking(n,k,1); return rslt; } public void backtracking(int n,int k,int startIdx) { //终止条件——收集结果 if(path.size()==k){ //注意不要直接add(path)！ rslt.add(new ArrayList<>(path)); return; } //递归逻辑——遍历的过程 //★横向遍历+优化循环终止条件 for(int i=startIdx;i<=n-(k-path.size())+1;i++){ path.add(i); //纵向遍历 backtracking(n,k,i+1); //回溯 path.remove(path.size()-1); } } }
-
（2）216. 组合总和 III
-
思路：整体思路与上面77.组合一样，只是多了遍历时求和的过程。要注意：
①求和时也要注意回溯！因为下一次for循环要用到sum；
②多了一个sum>n的剪枝操作，因为是从[1,9]中挑k个满足sum=n的组合，所以搜索过程中sum已经大于n了，后面的只会更大，所以不需要往后搜索了。
class Solution { List<List<Integer>> rslt=new ArrayList<List<Integer>>(); List<Integer> path=new ArrayList<Integer>(); public List<List<Integer>> combinationSum3(int k, int n) { backtracking(k,n,1,0); return rslt; } public void backtracking(int k,int n,int startIdx,int sum){ //剪枝 if(sum>n) return; //终止条件 if(path.size()==k){ if(sum==n){ rslt.add(new ArrayList<>(path)); } return; } //递归逻辑 //横向 for(int i=startIdx;i<=9-(k-path.size())+1;i++){ sum+=i; path.add(i); backtracking(k,n,i+1,sum);//纵向 //回溯 path.remove(path.size()-1); sum-=i;//★ } } }
（3）17.电话号码的字母组合
-
思路：首先要学会怎么把问题抽象成树型结构。树型结构是怎么来的呢？因为要横向+纵向遍历，所以才形成了树型结构。这道题的★横向遍历遍历digit中每个数字对应的字母串，纵向遍历就是就是遍历digit。
①确定返回值类型和参数
-- 返回值void。参数首先是digit，其次需要index来记录纵向遍历digit时要处理digit中的第几个数字。
②★终止条件
-- 递归处理完digit最后一个数字就结束，也就是说index要等于digit的长度。
③递归逻辑
-- 先通过index找到对应digit中的数字，再去映射数组中找该数字对应的字母串，然后遍历这个字母串。
class Solution { List<String> rslt=new ArrayList<String>(); StringBuilder path=new StringBuilder(); //数字0~9和字母的映射关系，下标从0开始，0、1对应空串，这样下标直接就是对应的数字。 String[] yingshe={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}; public List<String> letterCombinations(String digits) { if(digits==null||digits.length()==0){ return rslt; } backtracking(digits,0); return rslt; } //index表示取digits中的第几个数字，从0开始算。 public void backtracking(String digits,int index){ //★终止条件——如果取得数等于字符串长度，递归就结束。 if(index==digits.length()){ rslt.add(path.toString()); return; } //递归逻辑——处理每个数字的映射 //★digit中index对应的数字num int num=digits.charAt(index)-'0'; //digit中当前num对应的字母串 String s=yingshe[num]; //横向遍历字母串 for(int i=0;i<s.length();i++){ path.append(s.charAt(i)); //纵向遍历digit backtracking(digits,index+1); //回溯 path.deleteCharAt(path.length()-1); } } }
（4）39. 组合总和
-
思路：本题搜索的过程抽象成树形结构如下：
①递归参数
★这里还是需要startIdx来表示本次递归的横向遍历的起始位置。如果没有startIdx的话，会导致组合数重复，比如[2,2,3]与[3,2,2]！所以加了startIdx还相当于做了去重操作。
②终止条件
因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要总和超过target，就返回；总和等于target就加入结果集后返回。
③递归逻辑
★递归的时候下一层横向遍历的起始位置不用+1了！因为这道题同一个数字可以重复使用！
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<>(); int sum=0; public List<List<Integer>> combinationSum(int[] candidates, int target) { backtracking(candidates,target,0); return rslt; } //★这里还是需要startIdx来表示本次递归的横向遍历的起始位置。如果没有startIdx的话，会导致组合数重复，比如[2,2,3]与[3,2,2]！所以加了startIdx还相当于做了去重操作。 public void backtracking(int[] candidates,int target,int startIdx){ //终止条件 if(sum==target){ rslt.add(new ArrayList(path)); return; } if(sum>target){ return; } //递归逻辑 for(int i=startIdx;i<candidates.length;i++){ path.add(candidates[i]); sum+=candidates[i]; backtracking(candidates,target,i);//★★这里不用i+1了！因为这道题同一个数字可以重复使用！ path.remove(path.size()-1); sum-=candidates[i]; } } }★剪枝优化：对candidates进行升序排序后，如果下一层递归得到的sum(即★本层的sum+candidates[ i ])大于target，那么下一层就不需要继续进行横向遍历了。比如已经取了[2 ，2]了，此时sum=4，下一层递归bt(candidates,target,2)的sum=4+2=6>4了，就不需要再取[2，2 ，3]了。
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<>(); int sum=0; public List<List<Integer>> combinationSum(int[] candidates, int target) { //排序 Arrays.sort(candidates); backtracking(candidates,target,0); return rslt; } //★这里还是需要startIdx来表示本次递归的横向遍历的起始位置。如果没有startIdx的话，会导致组合数重复，比如[2,2,3]与[3,2,2]！所以加了startIdx还相当于做了去重操作。 public void backtracking(int[] candidates,int target,int startIdx){ //终止条件 if(sum==target){ rslt.add(new ArrayList(path)); return; } if(sum>target){ return; } //递归逻辑 //★剪枝优化：对candidates进行升序排序后,如果下一次递归的sum(即：本层的sum + candidates[i])已经大于target，就可以结束本轮for循环的遍历了。 for(int i=startIdx;i<candidates.length&&(sum+candidates[i])<=target;i++){ path.add(candidates[i]); sum+=candidates[i]; backtracking(candidates,target,i);//★★这里不用i+1了！因为这道题同一个数字可以重复使用！ path.remove(path.size()-1); sum-=candidates[i]; } } }
（5）40.组合总和II
-
思路：这道题与前面几道题最大的区别就是给的集合有重复元素，但是要求结果集中不能有重复组合，比如[1，7]和[7，1]就算重复组合，只能留一个。这就涉及到组合中的去重问题。我们知道在遍历时需要横向和纵向遍历，那么我们应该在什么横向去重，还是纵向去重，还是都要去重呢？
——应该在横向for循环中去重。比如下面的例子，集合为[1，1，2]，target为3。在第一层的横向遍历时，我们取了第一个1，然后进行纵向遍历后，就不需要再横向取第二个1了，因为这俩得到的组合都是以1开头的[1，...，...]，这就重复了。还有★去重需要先排序。
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<>(); public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); bt(candidates,target,0); return rslt; } public void bt(int[] candidates, int target,int startIdx){ if(target==0){ rslt.add(new ArrayList(path)); return; } //★剪枝 for(int i=startIdx;i<candidates.length&&candidates[i]<=target;i++){ if(i>startIdx&&candidates[i]==candidates[i-1]){ continue; } target-=candidates[i]; path.add(candidates[i]); bt(candidates,target,i+1); target+=candidates[i]; path.remove(path.size()-1); } } }
2.分割问题
（1）★93.复原IP地址
-
思路：分割问题。递归三部曲：
-
递归参数
因为不能重复分割，所以startIdx一定是需要的，用来记录下一层递归分割的起始位置。
本题我们还需要一个变量pointCount，用来记录添加"."的数量。 -
递归终止条件
本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
pointCount表示逗点数量，pointCount为3时说明字符串分成了4段了。然后验证一下第四段是否合法，如果合法就加入到结果集里。
-
单层搜索的逻辑
在for (int i = startIdx; i < s.length(); i++)循环中 [startIndex, i] 这个区间就是截取的子串，需要判断这个子串是否合法。
如果合法就在字符串后面加上符号.表示已经分割。
如果不合法就结束本层循环。
class Solution { List<String> rslt=new ArrayList<String>(); public List<String> restoreIpAddresses(String s) { backtracking(s,0,0); return rslt; } //★count用来记录已经加了几个"." public void backtracking(String s,int startIdx,int pointCount){ //终止条件 if(pointCount==3){ //判断第四段数字是否合法，合法加进去结束；不合法不用加，也结束 if(isValid(s,startIdx,s.length()-1)){ rslt.add(s); } return; } //横向遍历 for(int i=startIdx;i<s.length();i++){ //判断数字是否合法 if(isValid(s,startIdx,i)){//合法才加"." s = s.substring(0, i + 1) + "." + s.substring(i + 1);//插⼊⼀个"." pointCount++; backtracking(s, i + 2, pointCount);//★★插⼊"."之后i+1的位置是"."了，所以下⼀个⼦串的起始位置为i+2 // 回溯 pointCount--; s = s.substring(0, i + 1) + s.substring(i + 2);// 回溯删掉"." }else{//不合法就没有继续横向遍历的必要了 break; } } } //判断字符串s在左闭右闭区间[start, end]所组成的数字是否合法 public boolean isValid(String s,int start,int end){ if (start > end) { return false; } // 除了0以外，以0开头的数字不合法 if (s.charAt(start) == '0' && start != end) { //★start != end表示排除了0 return false; } int num = 0; for (int i = start; i <= end; i++) { //遇到⾮数字字符不合法 if (s.charAt(i) > '9' || s.charAt(i) < '0') { return false; } //★★将数字字符串转成对应int数字的方法 num = num * 10 + (s.charAt(i) - '0'); //⼤于255了不合法 if (num > 255) { return false; } } //都合法 return true; } } -
递归参数
3.子集问题
（1）78.子集
-
思路：子集问题。前面的组合和分割问题都是在收集树型结构的叶子节点，即在达到终止条件时收集结果，而子集是收集树中的每一个节点。
那么如何在递归中收集每一个节点呢？
——一个节点其实就是一层递归，即每一层递归都有我们想要的结果，所以需要在进入每一次递归时都收集结果。
求子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。
class Solution { List<List<Integer>> rslt=new ArrayList<List<Integer>>(); List<Integer> path=new ArrayList<>(); public List<List<Integer>> subsets(int[] nums) { bt(nums,0); return rslt; } public void bt(int[] nums,int startIdx){ //★每个节点都要收集进rslt //第一次bt收集的是空集，也就是说每一次bt收集的都是上一次的结果，所以rslt.add要在终止条件前面，这样才能保证把叶子节点也收集进去！ rslt.add(new ArrayList(path)); //终止条件 if(startIdx>=nums.length){ return; } //递归逻辑 for(int i=startIdx;i<nums.length;i++){ path.add(nums[i]); bt(nums,i+1); path.remove(path.size()-1); } } }
（2）90. 子集 II
-
思路：这道题与上一道题相比多了去重操作。牢记去重先排序！
class Solution { List<List<Integer>> rslt=new ArrayList<List<Integer>>(); List<Integer> path=new ArrayList<>(); public List<List<Integer>> subsetsWithDup(int[] nums) { //★去重先排序！ Arrays.sort(nums); bt(nums,0); return rslt; } public void bt(int[] nums,int startIdx){ rslt.add(new ArrayList(path)); if(startIdx>=nums.length){ return; } for(int i=startIdx;i<nums.length;i++){ //去重判断 if(i>startIdx&&nums[i]==nums[i-1]){ continue; }else{ path.add(nums[i]); bt(nums,i+1); path.remove(path.size()-1); } } } }
（3）491.递增子序列
-
思路：子集问题。本题也涉及到去重，但是这道题不能用以前的去重逻辑(排序+去重)来处理了！因为一旦排序，就对产生错误的递增序列。比如原序列是[4，7，6，7]，有重复元素。如果排序了，成了[4，6，7，7]，得到的递增子序列中会有[4，6，7，7]这个子集，而原序列[4，7，6，7]根本没有[4，6，7，7]这个子集！所以像这种排序后会影响结果的题目，就不能用排序去重了！
那么这道题该如何去重呢？
——使用set集合，取了的数放进set里，取数前先判断该数在不在set中，不在set中再取。
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<Integer>(); public List<List<Integer>> findSubsequences(int[] nums) { bt(nums,0); return rslt; } public void bt(int[] nums,int startIdx){ //对长度大于1的每个节点收集结果(递增序列至少两个元素) if(path.size()>1){ rslt.add(new ArrayList(path)); } //终止条件 if(startIdx>=nums.length){ return; } //递归逻辑 //★用来记录【本层递归，即横向遍历时】取得元素是否重复 Set<Integer> set=new HashSet<>(); for(int i=startIdx;i<nums.length;i++){ //★如果当前元素被取过了，直接跳过进入下一轮循环或者如果path中有元素且当前元素小于path最后一个元素，跳过，进入下一轮循环 if(set.contains(nums[i])||(path.size()!=0&&nums[i]<path.get(path.size()-1))){ continue; } //path为空或当前元素不小于path最后一个元素才往里放 path.add(nums[i]); set.add(nums[i]); bt(nums,i+1); path.remove(path.size()-1); //★这里不需要对set进行回溯!!!因为前面是在每层递归中都定义了一个set，用来记录本层递归是否重复取元素，也就是说横向遍历时需要去重，而递归是纵向遍历，所以不需要对set进行回溯!!! //set.remove(set.size()-1);←←←不需要!!! } } }
4.排列问题
（1）46.全排列
-
思路：无重复元素的序列排列问题。排列问题有顺序，对于序列[1，2，3]来说，[1，2]和[2，1]是不同的结果集，这说明1在取[1，2]时用过了，后面在取[2，1]时还要用到。所以在排序问题中不需要startIdx了，每次都从0开始横向遍历，用used数组来记录元素是否已经取过了。
是否需要回溯取决于是作用于横线遍历还是纵向遍历，像上面的【491.递增子序列】问题，set是用来记录横向遍历的，所以不用回溯；而这道题的used即记录横向遍历，又记录纵向遍历(可以定义成全局变量，也可以作为bt的参数)，所以就要回溯了。
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { //用来记录元素是否取过了，0没取过，1取过了 int[] used=new int[21]; bt(nums,used); return rslt; } public void bt(int[] nums,int[] used){ //终止条件 if(path.size()==nums.length){ rslt.add(new ArrayList(path)); return; } //递归逻辑 for(int i=0;i<nums.length;i++){ //横向从头取，取过的不能取 if(used[nums[i]+10]==1){ continue; } path.add(nums[i]); used[nums[i]+10]=1; bt(nums,used); path.remove(path.size()-1); //★纵向从头取，取过的不能取 used[nums[i]+10]=0; } } }
（2）47. 全排列 II
-
思路：有重复元素的序列排序问题。对于[1，1，2]来说，它的全排列是[1,1,2]、[1,2,1]、[2,1,1]。注意这里面虽然有重复的1，但这是不同位置上的1，所以不算重复，比如[1，2，1]中的两个1，分别是原序列[1，1，2]的第一个和第二个1。所以我们需要进行去重。在对[1，1，2]排序后，它的树型结构为：
class Solution { List<List<Integer>> rslt=new ArrayList<>(); List<Integer> path=new ArrayList<>(); public List<List<Integer>> permuteUnique(int[] nums) { boolean[] used=new boolean[nums.length]; Arrays.fill(used, false); Arrays.sort(nums); bt(nums,used); return rslt; } public void bt(int[] nums,boolean[] used){ //终止条件 if(path.size()==nums.length){ rslt.add(new ArrayList(path)); return; } //递归逻辑 for(int i=0;i<nums.length;i++){ //横向去重，且不取用过的：即如果当前元素与前一个元素相同，并且前一个元素已经被用过了，直接跳过 //used[i-1] == false，说明同⼀树层的nums[i - 1]使⽤过了 if(i>0&&nums[i]==nums[i-1]&&used[i-1]==false){ continue; } //纵向不取用过的 if(used[i]==false){ path.add(nums[i]); used[i]=true; bt(nums,used); path.remove(path.size()-1); used[i]=false; } } } }
（3）★332.重新安排行程
-
思路：这道题最终结果集只有一种情况，即一个行程，所以回溯函数的返回值不能是void了而是boolean！用来控制找到合适路径一直向上返回到最上层，找不到路径才需要回溯！同时这道题要求如果有多种行程要按字典顺序输出，所以我们要对tickes进行排序（注意compareTo()的使用！）。
class Solution { List<String> rslt=new ArrayList<>(); List<String> path=new ArrayList<>(); public List<String> findItinerary(List<List<String>> tickets) { //★将tickets按每个元素的第二个元素的字典顺序排序 Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1))); path.add("JFK");//起始机场JFK //用来记录机票是否用过了，1用了0没用 int[] used=new int[tickets.size()]; bt(tickets,used); return rslt; } //★★因为最终结果集只需要找到一个行程即可，所以返回值需要设置为boolean，只要找到合适行程就返回true到最上层 public boolean bt(List<List<String>> tickets,int[] used){ //终止条件——去往的机场数 = 机票数 + 1 将所有的航班可以串在一起 if(path.size()==tickets.size()+1){ //★这里不是add了！ rslt=new ArrayList<>(path); return true; } //横向遍历 for(int i=0;i<tickets.size();i++){ //如果当前票没用过且当前票的起点已经加入到path中的最后一个，即当前票的起点是上一次的终点 if(used[i]==0&&tickets.get(i).get(0).equals(path.get(path.size()-1))){ path.add(tickets.get(i).get(1)); used[i]=1; //★★递归 //只需要找到一个行程，找到之后全部返回true到最上层即可，不需要回溯了！ if(bt(tickets,used)==true){ return true; } //找不到合适行程才需要回溯！ //回溯 used[i]=0; path.remove(path.size()-1); } } //没有找到合适路径 return false; } }
【tips】compareTo()实现升序和降序排序：
5.棋盘问题
（1）★51. N 皇后
-
思路：棋盘问题。回溯中涉及到横向遍历和纵向遍历，而棋盘问题刚好是一个二维数组，正好对应横向和纵向遍历(以3×3的棋盘为例，如下图)。
class Solution { List<List<String>> rslt=new ArrayList<List<String>>(); public List<List<String>> solveNQueens(int n) { //★创建棋盘——相当于path char[][] chessboard = new char[n][n]; //先填充棋盘 for (char[] c : chessboard) { //一行一行地填充棋盘 Arrays.fill(c, '.');//★fill(c, '.'):将'.'赋值给c数组的每个元素 } //从棋盘的第0行开始搜索 bt(n,0,chessboard); return rslt; } public void bt(int n,int row,char[][] chessboard){ //终止条件 if(row==n){ rslt.add(Array2List(chessboard)); return; } //递归 //横向遍历 for(int i=0;i<n;i++){ //★判断皇后位置是否合法 if(isValid(row,i,n,chessboard)){ chessboard[row][i]='Q'; bt(n,row+1,chessboard); //★回溯——不回溯同一行就有多个皇后了! chessboard[row][i]='.'; } } } //★将棋盘转成题目要求的输出格式rslt public List Array2List(char[][] chessboard) { List<String> list = new ArrayList<>();//相当于一个path //一行一行地遍历 for (char[] c : chessboard) { //list中是["第一行","第二行","第三行",...] list.add(String.valueOf(c));//如果c是['.','Q','.','.']，那么String.valueOf(c)就是".Q.."，所以是把".Q.."放到list中 } return list; } //★判断第row行第col列的皇后在n×n的棋盘chessboard中是否合法(记住几个参数的含义!) public boolean isValid(int row,int col,int n,char[][] chessboard) { // 不用检查同行，因为我们每行只放了一个皇后! // 检查皇后所在列有无其他皇后 for (int i=0;i<row;i++) { // i<row相当于剪枝，因为row下面的行还没放皇后呢，所以一定没有其他皇后，因此i只需要小于row即可! if (chessboard[i][col] == 'Q') { return false; } } // 检查45度对角线，从皇后的左上角开始，检查到棋盘的左上角(同理，皇后右下对角线上一定没有其他皇后!) for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) { if (chessboard[i][j] == 'Q') { return false; } } // 检查135度对角线，从皇后的右上角开始，检查到棋盘的右上角(左下角对角线上一定没有其他皇后) for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) { if (chessboard[i][j] == 'Q') { return false; } } return true; } }
（2）★37. 解数独
-
思路：棋盘问题。这道题与N 皇后不同之处在于，N 皇后是每行放一个确定的Q，所以只需要判断放Q的位置即可；而解数独每个位置都要放数，因此不仅需要判断位置，还需要判断在该位置放1-9中的哪个数。
如何确定位置？
——两层for循环。
如何确定在该位置放1-9中的哪个数？
——使用回溯枚举，挨个试。也就是说这道题回溯函数 bt 就是用来判断当前位置要放的内容的。
★为什么这道题不需要终止条件？
——加终止条件是为了让递归停下来。解数独递归时，下一层的棋盘一定比上一层的棋盘多一个数，等棋盘填满了数说明找到结果了，递归自然就终止了，所以不需要终止条件！
——并且确定位置后，如果在该位置尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！那么就会直接返回false，这就是为什么即使没有终止条件也不会永远填不满棋盘而无限递归下去！
class Solution { public void solveSudoku(char[][] board) { bt(board); } public boolean bt(char[][] board){ //两层for循环遍历棋盘，确定要放数的位置 for(int i=0;i<board.length;i++){ for(int j=0;j<board[0].length;j++){ //如果是'.'，说明(i,j)这个位置要放数了 if(board[i][j]=='.'){ for(char k='1';k<='9';k++){//1-9用回溯挨个枚举，这里才真正用到回溯!!! if(isValid(i,j,k,board)==true){ board[i][j]=k; if(bt(board)==true){ return true; } board[i][j]='.'; } } //走到这里说明9个数都试完了还没return true，那就说明没有答案了，需要返回false return false; } } } //走到这里说明所有位置都能填上正确的数，问题解决了，返回true。 return true; } public boolean isValid(int row,int col,char k,char[][] board){ //判断所在行有无重复数字 for(int i=0;i<board.length;i++){ if(board[row][i]==k){ return false; } } //判断所在列有无重复数字 for(int i=0;i<board.length;i++){ if(board[i][col]==k){ return false; } } //判断所在9宫格有无重复元素 //★确定起始位置 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]==k){ return false; } } } return true; } }优化：每次从当前行的下一列开始：class Solution { public void solveSudoku(char[][] board) { bt(0,0,board); } public boolean bt(int row,int col,char[][] board){ //优化：每次从当前行的下一列开始 for(int i=row;i<board.length;i++){ for(int j=col;j<board[0].length;j++){ if(board[i][j]=='.'){ for(char k='1';k<='9';k++){ if(isValid(i,j,k,board)==true){ board[i][j]=k; //优化：每次从当前行(i)的下一列(j+1)开始 if(bt(i,j+1,board)==true){ return true; } board[i][j]='.'; } } return false; } } //★所有列遍历完了再从第一列(col=0)开始,所以在列的for循环后面要重置列 col=0; } return true; } public boolean isValid(int row,int col,char k,char[][] board){ for(int i=0;i<board.length;i++){ if(board[row][i]==k){ return false; } } for(int i=0;i<board.length;i++){ if(board[i][col]==k){ 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]==k){ return false; } } } return true; } }
6.22. 括号生成
-
思路：
class Solution { List<String> res=new ArrayList<>(); StringBuilder path=new StringBuilder(); public List<String> generateParenthesis(int n) { //n其实就代表了左右括号【各有】几个 dfs(n,n); return res; } /** left:左括号剩余量 right:右括号剩余量 path:一次dfs的括号组合 */ public void dfs(int left,int right){ if(left==0&&right==0){ res.add(path.toString()); return; } //一定是先拼左括号再拼右括号 //如果左括号有剩余 if(left>0){ path.append("("); dfs(left-1,right); //回溯 path.deleteCharAt(path.length()-1); } //★这里不是if(right>0)!因为右括号有剩余不一定能拼,比如n=2,path="()",left=right=1,此时再拼不能拼)了，因为())不符合要求。也就是说，剩余右括号要大于剩余左括号的数量才能拼")"! if(right>left){ path.append(")"); dfs(left,right-1); //回溯 path.deleteCharAt(path.length()-1); } } }
7.
