【Java】HOT100 回溯

理论基础

一、组合问题

LeetCode77：组合

LeetCode17：电话号码的字母组合

LeetCode39：组合总和

LeetCode216：组合总和ii

LeetCode216：组合总和iii

二、分割问题

LeetCode131：分割回文串

LeetCode93：复原IP地址

三、子集问题

LeetCode78：子集

LeetCode90：子集ii

LeetCode491：递增子序列

四、排列问题

LeetCode46：全排列

LeetCode47：全排列ii

五、棋盘问题

LeetCode51：N皇后

LeetCode37：解数独

六、其他

LeetCode332：重新安排行程

理论基础

参考代码随想录的题型总结

定义：回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

虽然回溯法很难，很不好理解，但是回溯法并不是什么高效的算法。

因为回溯的本质是穷举，穷举所有可能，然后选出我们想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。它适用于只能够暴力搜索的问题，

如

组合问题：N个数里面按一定规则找出k个数的集合

分割问题：一个字符串按一定规则有几种切割方式

子集问题：一个N个数的集合里有多少符合条件的子集

排列问题：N个数按一定规则全排列，有几种排列方式

棋盘问题：N皇后，解数独等等

回溯法解决的问题都可以抽象为树形结构。 因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

回溯三部曲：返回值（通常是void）和传入参数、终止条件、单层搜索过程（类似递归三部曲）

模板框架如下：

java">void backtracking(参数) {if (终止条件) {存放结果;return;}for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {处理节点;backtracking(路径，选择列表); // 递归回溯，撤销处理结果}
}

一、组合问题

LeetCode77：组合

给出n和k，返回[1,n]区间内所有可能的k个数组合

思路：要解决 n为100，k为50的情况，暴力写法需要嵌套50层for循环，那么回溯法就用递归来解决嵌套层数的问题。抽象为树形结构（N叉树），相当于n相当于树的宽度，k相当于树的深度。每次搜索到了叶子节点，我们就找到了一个结果。

看回溯三部曲：返回值（通常是void）和传入参数、终止条件、单层搜索的过程

两个全局变量（单一结果path和结果集合res）、传入参数除了n、k，还有startIndex，用来记录下一层递归搜索的起始位置。
终止条件：到叶子结点（有个数要求所以终止条件是path.size() == k）

java">if (path.size() == k) {result.push_back(path);return;
}

单层搜索（for循环用来横向遍历，每次从startIndex开始遍历，然后用path保存取到的节点i。递归的过程是纵向遍历。）
剪枝（有个数要求：如果for循环选择的起始位置之后的元素个数已经不足我们需要的元素个数了，那么就没有必要搜索了）
记得res添加的是path对象的引用：result.add(new ArrayList<>(path));
以及res和path放在全局里就不用作为参数反复调用了

java">for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置

完整代码：

java">class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combine(int n, int k) {combineHelper(n, k, 1);return result;}/*** 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围，就是要靠startIndex* @param startIndex 用来记录本层递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）。*/private void combineHelper(int n, int k, int startIndex){//终止条件if (path.size() == k){result.add(new ArrayList<>(path));return;}for (int i = startIndex; i <= n - (k - path.size()) + 1; i++){path.add(i);combineHelper(n, k, i + 1);path.removeLast();}}
}

LeetCode17：电话号码的字母组合

思路：（1）数字和字母通过字符串数组来映射；（2）注意这里for循环，可不像是在和回溯算法：求组合总和！中从startIndex开始遍历的。因为本题每一个数字代表的是不同集合，也就是求不同集合之间的组合，而77. 组合和216.组合总和III 都是求同一个集合中的组合！

java">class Solution {List<String> list = new ArrayList<>();  //结果集public List<String> letterCombinations(String digits) {if(digits == null || digits.length() == 0){return list;}String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxz"};backTracking(digits,numString,0);return list;}StringBuilder tmp = new StringBuilder();    //临时结果public void backTracking(String digits, String[] numString, int num){//终止条件if(num == digits.length()){list.add(tmp.toString());return;}//单层搜索String str = numString[digits.charAt(num)-'0'];//为了使2对应abcfor(int i = 0 ;i<str.length();i++){tmp.append(str.charAt(i));backTracking(digits,numString,num+1);tmp.deleteCharAt(tmp.length()-1);}}
}

LeetCode39：组合总和

给出candidates数组（无重复元素，无限制重复选取）和target值，返回组合（无可重复）

思路：首先对candidaes数组排序（1）一个集合，用startindex（2）终止条件：到叶子结点==target加入res，sum>target直接return（不符合条件）（3）由于可重复选取，所以回溯不用i+1，从i开始，表示可重复选取（4）path回溯的同时记得sum也要跟着回溯（如果把sum加入参数则无需对sum进行+-，直接传递sum+candidates[i]即可，如果把sum作为全局变量则需要自己对sum进行+和-）（5）剪枝：在回溯循环内加入如果下一层的sum>target，就直接终止遍历，不用向下层遍历。

在求和问题中，排序之后加剪枝是常见的套路！

java">class Solution {List<List<Integer>> res = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {int sum = 0;int startIndex = 0;Arrays.sort(candidates);backTracking(candidates,target,sum,startIndex);return res;}public void backTracking(int[] candidates, int target, int sum, int startIndex){if(sum == target){res.add(new ArrayList(path));return;}for(int i=startIndex;i<candidates.length;i++){if(sum + candidates[i]>target){break;}path.add(candidates[i]);backTracking(candidates,target,sum + candidates[i],i);path.removeLast();}}
}

LeetCode216：组合总和ii

给出candidates数组（可能有重复元素，同一元素只能一次）和target值，返回组合（不可重复）

思路：重复数组的去重相当于同一树层的去重，不同树层可以用相等的元素

并且用一个bool类型的数组used来记录同一树枝上的元素是否使用过。（也可以不用标志数组）

java">for ( int i = start; i < candidates.length && sum + candidates[i] <= target; i++ )
//上一句直接覆盖了
if (sum + candidates[i] > target) {break;
}

最终代码：

java">class Solution {List<List<Integer>> res = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum2( int[] candidates, int target ) {//为了将重复的数字都放到一起，所以先进行排序int sum = 0;Arrays.sort( candidates );backTracking( candidates, target,sum, 0 );return res;}private void backTracking( int[] candidates, int target, int sum, int start ) {if ( sum == target ) {res.add( new ArrayList<>( path ) );return;}for ( int i = start; i < candidates.length; i++ ) {if (sum + candidates[i] > target) {break;}//正确剔除重复解的办法：跳过同一树层使用过的元素if ( i > start && candidates[i] == candidates[i - 1] ) {continue;}path.add( candidates[i] );// i+1 代表当前组内元素只选取一次backTracking(candidates, target, sum + candidates[i],i + 1 );path.removeLast();}}
}

LeetCode216：组合总和iii

给出总和n和个数k，返回组合（不重复的1-9，每个数字只能用一次）

思路：类似77，不过77是从【1，n】选取，本题是从【1,9】选取，且终止条件为sum==n。

和77. 组合问题差别不大

java">class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum3(int k, int n) {backTracking(n, k, 1, 0);return result;}private void backTracking(int target, int k, int startIndex, int sum) {     //终止条件if (path.size() == k) {if (sum == target) result.add(new ArrayList<>(path));return;}// 剪枝2： 9 - (k - path.size()) + 1for (int i = startIndex; i <= 9 - (k - path.size()) + 1; i++) {if (sum+i > target) {    //剪枝1后移break;}path.add(i);backTracking(target, k, i + 1, sum+i);path.removeLast();}}
}

二、分割问题

LeetCode131：分割回文串

思路：切割问题也类似树形结构，以startindex作为切割线，以【startindex，i】作为子串

最简单的做法（自己写的，无优化）（优化可以通过动态规划判断是否是回文串）

java">class Solution {List<List<String>> res = new ArrayList<>();List<String> path = new LinkedList<>();public List<List<String>> partition(String s) {backTracking(s,0);return res;}public void backTracking(String s, int start){if(start >= s.length()){res.add(new ArrayList<>(path));return;}for(int i = start;i<s.length();i++){String str = s.substring(start,i+1);if(isPalindrome(str)){path.add(str);}else{continue;}backTracking(s,i+1);path.removeLast();}}public boolean isPalindrome(String str){int left = 0;int right = str.length()-1;while(left<right){if(str.charAt(left++) != str.charAt(right--)){return false;}}return true;}
}

LeetCode93：复原IP地址

思路：就像组合总和题型以sum作为传递参数一样，IP地址将以dotsum作为传递参数，来判断是否回溯结束;用stringbuilder类型可直接通过insert函数修改，无需反复利用s字符串

isValid函数有三个条件：1. 子字段首位不为0；2. 大小在0-255；3. 每个数字都在0-9区间（不包含特殊字符）

java">class Solution {List<String> res = new ArrayList<>();public List<String> restoreIpAddresses(String s) {StringBuilder sb = new StringBuilder(s);backTracking(sb,0,0);return res;}public void backTracking(StringBuilder sb, int start, int dotNum){if(dotNum == 3){if(isValid(sb,start,sb.length()-1)){res.add(sb.toString());}return;}for(int i = start;i<sb.length() && i-start<3;i++){if(isValid(sb,start,i)){String str = sb.substring(start,i+1);sb.insert(i+1,'.');backTracking(sb,i+2,dotNum+1);sb.deleteCharAt(i+1);}else{break;}}}public boolean isValid(StringBuilder sb, int start, int end){if(start>end){return false;}if(sb.charAt(start)=='0' && start != end){return false;}int num = 0;for(int i =start;i<= end;i++){//记得转换类型，char-》intint digit = sb.charAt(i) - '0';if(digit<0 || digit>9){return false;}num = num*10 + digit;if(num<0 ||num>255){return false;}}return true;}
}

三、子集问题

LeetCode78：子集

给定一组不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点！求取子集问题，不需要任何剪枝！因为子集就是要遍历整棵树。（在注释中，可以发现可以不写终止条件，因为本来我们就要遍历整棵树。）

思路：path在每一个节点收集，得到子集结果path，每次回溯res都加入一个子集path

java">class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果public List<List<Integer>> subsets(int[] nums) {subsetsHelper(nums, 0);return result;}private void subsetsHelper(int[] nums, int startIndex){result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。if (startIndex >= nums.length){ //终止条件可不加return;}for (int i = startIndex; i < nums.length; i++){path.add(nums[i]);subsetsHelper(nums, i + 1);path.removeLast();}}
}

LeetCode90：子集ii

思路：相当于40组合总和ii和78子集的结合。稍微改一点

//为了将重复的数字都放到一起，要先进行排序，然后在for循环里进行去重。

java">class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果public List<List<Integer>> subsetsWithDup(int[] nums) {Arrays.sort(nums);subsetsHelper(nums, 0);return result;}private void subsetsHelper(int[] nums, int startIndex){result.add(new ArrayList<>(path));//「遍历这个树的时候，把所有节点都记录下来，就是要求的子集集合」。if (startIndex >= nums.length){ //终止条件可不加return;}for (int i = startIndex; i < nums.length; i++){if(i>startIndex && nums[i] == nums[i-1]){continue;}path.add(nums[i]);subsetsHelper(nums, i + 1);path.removeLast();}}
}

LeetCode491：递增子序列

由于根据代码随想录说491和90子集ii很类似，所以就放在一起讨论

思路：子集＋去重，和子集ii非常类似，但是由于求递增子序列，不能对nums进行排序来去重。

那如何去重呢？可以用set记录加入过的元素。数组，set，map都可以做哈希表，而且数组干的活，map和set都能干，但如果数值范围小的话能用数组尽量用数组，耗时效果会更好。

终止条件：递增子序列的长度至少是2

跳过条件：nums[i]小于子集最后一个，不构成递增，或者该元素已经添加过（同一层）

java">class Solution {List<List<Integer>> result = new ArrayList<>();List<Integer> path = new ArrayList<>();public List<List<Integer>> findSubsequences(int[] nums) {backTracking(nums, 0);return result;}private void backTracking(int[] nums, int startIndex){if(path.size() >= 2)result.add(new ArrayList<>(path));            HashSet<Integer> hs = new HashSet<>();for(int i = startIndex; i < nums.length; i++){if(!path.isEmpty() && path.get(path.size() -1 ) > nums[i] || hs.contains(nums[i]))continue;hs.add(nums[i]);path.add(nums[i]);backTracking(nums, i + 1);path.remove(path.size() - 1);}}
}

四、排列问题

LeetCode46：全排列

不重复序列nums的全排列

思路：①排列无需用startindex，每层都是从0开始搜索，因为排列是有序的。②但他又需要一个used数组（或者直接用list.contains判断，但数组更快），因为他不能重复使用元素，一个排列里一个元素只能使用一次。

java">class Solution {List<List<Integer>> result = new ArrayList<>();// 存放符合条件结果的集合LinkedList<Integer> path = new LinkedList<>();// 用来存放符合条件结果boolean[] used;public List<List<Integer>> permute(int[] nums) {if (nums.length == 0){return result;}used = new boolean[nums.length];permuteHelper(nums);return result;}private void permuteHelper(int[] nums){if (path.size() == nums.length){result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++){if (used[i]){continue;}used[i] = true;path.add(nums[i]);permuteHelper(nums);path.removeLast();used[i] = false;}}
}

LeetCode47：全排列ii

可重复数字序列的全排列

思路：首先要去重，去重就要先sort，然后对同一树层进行去重，即

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

// used[i - 1] == true，说明同⼀树⽀nums[i - 1]使⽤过
// used[i - 1] == false，说明同⼀树层nums[i - 1]使⽤过
// 如果同⼀树层nums[i - 1]使⽤过则直接跳过

代码：

java">class Solution {//存放结果List<List<Integer>> result = 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);backTrack(nums, used);return result;}private void backTrack(int[] nums, boolean[] used) {if (path.size() == nums.length) {result.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; 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;}//如果同⼀树⽀nums[i]没使⽤过开始处理if (used[i] == false) {used[i] = true;//标记同⼀树⽀nums[i]使⽤过，防止同一树枝重复使用path.add(nums[i]);backTrack(nums, used);path.remove(path.size() - 1);//回溯，说明同⼀树层nums[i]使⽤过，防止下一树层重复used[i] = false;//回溯}}}
}

五、棋盘问题

LeetCode51：N皇后

思路：1. 以行row来遍历，传递参数有n，row，还有string；2. 终止条件是row==n，3. 单层递归是：先判断是否满足约束，再放置棋子

由于每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
new String(c)和String.copyValueOf(c)作用相同，都是创建一个新的字符串对象，其中包含了字符数组 c 所包含的字符序列

java">class Solution {List<List<String>> res = new ArrayList<>();public List<List<String>> solveNQueens(int n) {char[][] chessboard = new char[n][n];//先填满'.'，再改变个别for (char[] c : chessboard) {Arrays.fill(c, '.');}backTrack(n, 0, chessboard);return res;}public void backTrack(int n, int row, char[][] chessboard) {if (row == n) {List<String> list = new ArrayList<>();for (char[] c : chessboard) {list.add(new String(c));}res.add(list);return;}for (int col = 0;col < n; col++) {if (isValid (row, col, n, chessboard)) {chessboard[row][col] = 'Q';backTrack(n, row+1, chessboard);chessboard[row][col] = '.';}}}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;}}// 检查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;}
}

LeetCode37：解数独

思路：与N皇后不同，N皇后的每一行只需要放一个棋子，是一维递归，而解数独的每一个位置都需要放置一个数字，是二维递归，并检查是否valid。由于不要求找到所有可能的解，因此找到一个解到叶子结点就返回，且本题就像子集问题一样，也无需加终止条件，因为本来也要遍历整棵树。

java">class Solution {public void solveSudoku(char[][] board) {solveSudokuHelper(board);}private boolean solveSudokuHelper(char[][] board){//「一个for循环遍历棋盘的行，一个for循环遍历棋盘的列，// 一行一列确定下来之后，递归遍历这个位置放9个数字的可能性！」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++){ // (i, j) 这个位置放k是否合适if (isValidSudoku(i, j, k, board)){board[i][j] = k;if (solveSudokuHelper(board)){ // 如果找到合适一组立刻返回return true;}board[i][j] = '.';}}// 9个数都试完了，都不行，那么就返回falsereturn false;// 因为如果一行一列确定下来了，这里尝试了9个数都不行，说明这个棋盘找不到解决数独问题的解！// 那么会直接返回， 「这也就是为什么没有终止条件也不会永远填不满棋盘而无限递归下去！」}}// 遍历完没有返回false，说明找到了合适棋盘位置了return true;}/*** 判断棋盘是否合法有如下三个维度:*     同行是否重复*     同列是否重复*     9宫格里是否重复*/private boolean isValidSudoku(int row, int col, char val, 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;}}// 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] == val){return false;}}}return true;}
}

六、其他

LeetCode332：重新安排行程

思路：一般讲解回溯算法的时候，一般函数返回值都是void，这次为什么是bool呢？因为它要处理递归函数的返回值。对于一个机场到多个机场的映射，机场之间要靠字母序排列（在字母顺序排序中，会逐个比较字符串中的字符）。

用map<出发机场, map<到达机场, 航班次数>>映射，可以使用"航班次数"这个字段的数字做相应的增减，来标记到达机场是否使用过了。如果“航班次数”大于零，说明目的地还可以飞，如果“航班次数”等于零说明目的地不能飞了，而不用对集合做删除元素或者增加元素的操作。

回溯三部曲：

1. 传入ticketsum，返回boolean类型; 2. 终止条件：ticketsum+1==res.size(); 3. 单层回溯：遍历每一层（即每个res.last对应的目的地），判断航班次数》0则向res里添加目的地，进行回溯。

java">class Solution {private Deque<String> res = new LinkedList<>();;private Map<String, Map<String, Integer>> map = new HashMap<String, Map<String, Integer>>();public List<String> findItinerary(List<List<String>> tickets) {//1.首先添加所有tickes进mapfor (List<String> t : tickets) {Map<String, Integer> temp;if (map.containsKey(t.get(0))) {temp = map.get(t.get(0));temp.put(t.get(1), temp.getOrDefault(t.get(1), 0) + 1);} else {temp = new TreeMap<>();// 升序Maptemp.put(t.get(1), 1);}map.put(t.get(0), temp);}//接着初始化结果队列res.add("JFK");backTracking(tickets.size());return new ArrayList<>(res);}private boolean backTracking(int ticketNum) {if (res.size() == ticketNum + 1) {return true;}String last = res.getLast();    //得到最后一个地点if (map.containsKey(last)) {// 防止出现null//last-map对应的每个target<目的地，航班次数>for (Map.Entry<String, Integer> target : map.get(last).entrySet()) {int count = target.getValue();if (count > 0) {res.add(target.getKey());    //以最后一个地点为起点的目的地target.setValue(count - 1);if (backTracking(ticketNum))return true;res.removeLast();target.setValue(count);}}}return false;}
}