行业知识
LeetCode——回溯算法(Java)
2026-11-06 02:52:43
来源：互联网转载
回溯算法
- 简介
- [中等] 77. 组合
- [中等] 216. 组合总和 III
- [中等] 17. 电话号码的字母组合
- [中等] 39. 组合总和
- [中等] 40. 组合总和 II
- [中等] 131. 分割回文串
- [中等] 93. 复原 IP 地址
- [中等] 78. 子集
- [中等] 90. 子集 II
- [中等] 491. 非递减子序列
- [中等] 46. 全排列
- [中等] 47. 全排列 II
- [困难] 51. N 皇后
- [困��] 37. 解数独
简介
记录一下自己刷题的历程以及代码。写题过程中参考了 代码随想录的刷题路线。会附上一些个人的思路，如果有错误，可以在评论区提醒一下。
回溯题模板：
class Solution { public 主方法(参数) { //把递归参数传入递归函数 recursion(0); return ans; } public void recursion(int n){ if(达到终止条件) { //存放结果 ans.add(answer); return; } for(循环调用后续的递归){ //递归前处理，比如把当前数加入答案集合 recursion(n + 1); //递归后处理，回溯，撤销递归前处理的内容 } }}[中等] 77. 组合
原题链接
注意每次ans.add（）时需要添加nums的深拷贝，而不是单纯把当前nums放入，否则放入的其实是nums数组的引用，最后ans的所有元素实际都指向了同一个数组。
class Solution { public List combine(int n, int k) { List ans = new ArrayList(); List nums = new ArrayList(); recursion(ans, nums, 1, n, k); return ans; } public void recursion(List ans, List nums, int p, int n, int k){ //终止条件 if(nums.size() == k){ ans.add(new ArrayList(nums)); return; } for(; p nums.add(p); recursion(ans, nums, p+1, n, k); nums.remove(nums.size() - 1); } return; }} nums.add(p); recursion(ans, nums, p+1, n, k); nums.remove(nums.size() - 1); } public List List if(nums.size() == k){ if(sum(nums) == n) ans.add(new ArrayList for (; p nums.add(p); recursion(ans, nums, k, n, p + 1); nums.remove(nums.size() - 1); } } } public int sum(List int sum = 0; for(Integer i: nums){ sum += i; } return sum; }} public List StringBuilder sb = new StringBuilder(); List"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}; if(digits.length() == 0) return ans; recursion(digits, sb, ans, numString, 0); return ans; } public void recursion(String digits, StringBuilder sb, List if(p == digits.length()){ ans.add(sb.toString()); return; } for(int i = 0; i[中等] 131. 分割回文串
原题链接
这个递归自己想还想了挺久的，就是从左往右切割，终止条件就是判断有没有切到最右端
class Solution { public List partition(String s) { List ans = new ArrayList(); List group = new ArrayList(); if(s == null || s.length() == 0) return ans; recursion(ans, group, s, 0); return ans; } private void recursion(List ans, List group, String s, int start) { if(start == s.length()) { ans.add(new ArrayList(group)); return; } for(int i = start; i[中等] 93. 复原 IP 地址
原题链接
注意分割段到4时也需要return，往后的递归都是无意义的
class Solution { public List restoreIpAddresses(String s) { List ans = new ArrayList(); List answer = new ArrayList(); if(s == null || s.length() == 0) return ans; //p表示目前划分到第几段，ip地址总共四段， index表示s下标 recursion(ans, s, 0, answer); return ans; } public void recursion(List ans, String s, int index, List answer){ if(answer.size() == 4 && index == s.length()){ ans.add(createAnswer(answer)); } if(index == s.length() || answer.size() == 4) return; if(s.charAt(index) == '0'){ answer.add("0"); recursion(ans, s, index + 1, answer); answer.remove(answer.size() - 1); }else { for (int i = index; i[中等] 491. 非递减子序列
原题链接
不能简单的强制类似[1,1,1,1,1]序列从左到右选，这道题不能排序，有可能会有[1,1,2,1,1]，这样2之前的1没取的时候2后面的1也可以取，需要用集合set来做去重
class Solution { public List findSubsequences(int[] nums) { List ans = new ArrayList(); List answer = new ArrayList(); recursion(ans, answer, nums, 0); return ans; } public void recursion(List ans, List answer, int[] nums, int index){ if(answer.size() > 1) ans.add(new ArrayList(answer)); HashSet hs = new HashSet(); for(int i = index; i 0 && nums[i][中等] 46. 全排列
原题链接
开一个数组标记不重复取数，每次循环都从头开始即可
class Solution { public List permute(int[] nums) { List ans = new ArrayList(); List answer = new ArrayList(); boolean[] used = new boolean[nums.length]; recursion(ans, answer, used, nums); return ans; } public void recursion(List ans, List answer, boolean[] used, int[] nums){ if(answer.size() == nums.length) { ans.add(new ArrayList(answer)); return; } for(int i = 0; i[中等] 47. 全排列 II
原题链接
对数组排序，并对相同数字，保证从左到右取数，同时不重复取数
class Solution { public List permuteUnique(int[] nums) { List ans = new ArrayList(); List answer = new ArrayList(); boolean[] used = new boolean[nums.length]; Arrays.sort(nums); recursion(ans, answer, used, nums); return ans; } public void recursion(List ans, List answer, boolean[] used, int[] nums){ if(answer.size() == nums.length) { ans.add(new ArrayList(answer)); return; } for(int i = 0; i 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue; used[i] = true; answer.add(nums[i]); recursion(ans, answer, used, nums); answer.remove(answer.size() - 1); used[i] = false; } }}[困难] 51. N 皇后
原题链接
class Solution { public List solveNQueens(int n) { List ans = new ArrayList(); //初始化棋盘，声明一个flag数组，标记每一行填充的元素在哪一列，初始化为-1 int[] flag = new int[n]; for(int i = 0; i[困难] 37. 解数独
原题链接
代码随想录给到的是一种暴力二维搜索，是比较容易想到的，每次递归都去判断行、列、九宫格里是否重复，这样效率会比较低，可以牺牲空间来简化这部分的判断，分别开设三个二维数组，记录每一行每一列每一个九宫格，1-9的数字是否被使用过，后续比较直接从数组里去读取信息就可以。
class Solution { public void solveSudoku(char[][] board) { //行、列、九宫格是否被占用 boolean[][] rowOccupy = new boolean[9][9]; boolean[][] colOccupy = new boolean[9][9]; boolean[][] nineOccupy = new boolean[9][9]; char a = board[1][2]; for(int i = 0; i 8 || j > 8) return true; if(board[i][j] != '.'){ if(j == 8) { if (recursion(rowOccupy, colOccupy, nineOccupy, board, i + 1, 0)) { return true; } } else if (recursion(rowOccupy, colOccupy, nineOccupy, board, i, j + 1)) { return true; } }else { for (int k = 1; k if (!rowOccupy[i][k - 1] && !colOccupy[j][k - 1] && !nineOccupy[i / 3 * 3 + j / 3][k - 1]) { board[i][j] = String.valueOf(k).charAt(0); rowOccupy[i][k - 1] = true; colOccupy[j][k - 1] = true; nineOccupy[i / 3 * 3 + j / 3][k - 1] = true; if (j == 8) { if (recursion(rowOccupy, colOccupy, nineOccupy, board, i + 1, 0)) { return true; } } else if (recursion(rowOccupy, colOccupy, nineOccupy, board, i, j + 1)) { return true; } board[i][j] = '.'; rowOccupy[i][k - 1] = false; colOccupy[j][k - 1] = false; nineOccupy[i / 3 * 3 + j / 3][k - 1] = false; } } } return false; }}
