一 回溯三部曲
1 递归函数的返回值以及参数
2 回溯函数终止条件
3 单层搜索的过程
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}模板题
组合
import java.util.ArrayList;
import java.util.List;
class Solution {
// 用于存储单个组合中的数字
List<Integer> singleRet = new ArrayList<>();
// 用于存储所有组合的列表
List<List<Integer>> ret = new ArrayList<>();
// 主函数，接收两个参数n和k，分别表示数字的范围和需要选取的数字数量
public List<List<Integer>> combine(int n, int k) {
// 从1开始递归生成组合
Demo(n, k, 1);
// 返回所有组合的列表
return ret;
}
// 递归函数，用于生成组合
void Demo(int n, int k, int startIndex) {
// 如果当前组合的长度已经等于k，说明找到了一个有效的组合，将其添加到结果列表中
if (singleRet.size() == k) {
ret.add(new ArrayList<>(singleRet));
return;
}
// 从startIndex开始，尝试每一种可能的数字
for (int i = startIndex; i <= n; i++) {
// 将当前数字添加到当前组合中
singleRet.add(i);
// 递归调用Demo函数，尝试在当前组合的基础上继续添加数字
Demo(n, k, i + 1);
// 回溯步骤，从当前组合中移除最后一个数字，尝试其他可能的数字
singleRet.remove(singleRet.size() - 1);
}
}
}二 组合问题
要startIndex的情况
如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合
组合总和III
无重复元素数组中，处理同一个数组，深度中不使用已经使用过的元素
class Solution {
// 存储所有符合条件的组合结果
List<List<Integer>> ret = new ArrayList<>();
// 当前路径，存储当前组合
List<Integer> path = new ArrayList<>();
// 当前路径的和
int pathSum = 0;
public List<List<Integer>> combinationSum3(int k, int n) {
// 从数字1开始进行组合，调用递归方法
Demo(k, n, 1);
return ret; // 返回所有符合条件的组合
}
void Demo(int k, int n, int startIndex) {
// 收获结果
// 检查当前路径的大小是否等于k，并且路径的和是否等于n
if (path.size() == k && pathSum == n) {
// 如果满足条件，则将当前路径的副本添加到结果列表中
ret.add(new ArrayList<>(path));
return; // 结束当前递归
}
// 深度遍历，尝试从startIndex到9的每个数字
for (int i = startIndex; i <= 9; i++) {
// 处理节点：将当前数字添加到路径中
path.add(i);
pathSum += i; // 更新路径的和
// 递归调用，继续选择下一个数字
Demo(k, n, i + 1);
// 回溯：移除当前数字，恢复状态
path.remove(path.size() - 1);
pathSum -= i; // 更新路径的和，减去当前数字
}
}
}电话号码的字母组合
无重复元素数组中，处理不同的数组，深度中不使用已经使用过的元素
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
class Solution {
// 用于存储最终的字母组合结果
List<String> ret = new ArrayList<>();
// 用于存储数字到字母的映射关系
Map<Integer, String> map;
// 用于构建当前的字母组合
StringBuilder sb = new StringBuilder();
/**
* 根据输入的数字字符串生成所有可能的字母组合
*
* @param digits 输入的数字字符串
* @return 生成的所有字母组合列表
*/
public List<String> letterCombinations(String digits) {
// 如果输入的字符串为空或者为null，则直接返回空列表
if (digits == null || digits.length() == 0) {
return ret;
}
// 初始化数字与字母的映射关系
map = new HashMap<>();
map.put(2, "abc");
map.put(3, "def");
map.put(4, "ghi");
map.put(5, "jkl");
map.put(6, "mno");
map.put(7, "pqrs");
map.put(8, "tuv");
map.put(9, "wxyz");
// 从输入字符串的第一个数字开始递归生成字母组合
Demo(digits, 0);
return ret;
}
/**
* 递归方法，用于生成字母组合
*
* @param digits 输入的数字字符串
* @param num 当前处理的数字字符串的索引
*/
void Demo(String digits, int num) {
// 如果当前索引已经到达输入字符串的末尾，则将当前构建的字母组合添加到结果列表中
if (num == digits.length()) {
ret.add(sb.toString());
return;
}
// 获取当前数字对应的字母字符串
int index = digits.charAt(num) - '0';
String str = map.get(index);
// 遍历当前数字对应的所有字母，并递归生成后续的字母组合
for (int i = 0; i < str.length(); i++) {
sb.append(str.charAt(i)); // 将当前字母添加到构建的字母组合中
Demo(digits, num + 1); // 递归调用，处理下一个数字
sb.deleteCharAt(sb.length() - 1); // 回溯，移除最后一个字母，以便尝试下一个字母
}
}
}组合总和
无重复元素数组中，处理同一个数组，深度中可重复选取已经使用过的元素
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
// 用于存储所有可能的组合结果
List<List<Integer>> ret = new ArrayList<>();
// 用于存储当前的组合路径
List<Integer> path = new ArrayList<>();
/**
* 组合求和问题的解法
*
* @param candidates 候选数字数组
* @param target 目标数字
* @return 所有可能的组合列表
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 如果候选数组为空或长度为0，则直接返回空结果
if (candidates == null || candidates.length == 0) {
return ret;
}
// 对候选数组进行排序，以便后续去重和剪枝
Arrays.sort(candidates);
// 从索引0开始，和为0的情况下开始递归搜索
Demo(candidates, target, 0, 0);
return ret;
}
/**
* 递归方法，用于搜索所有可能的组合
*
* @param candidates 候选数字数组
* @param target 目标数字
* @param startIndex 当前搜索的起始索引
* @param sum 当前路径的数字和
*/
void Demo(int[] candidates, int target, int startIndex, int sum) {
// 如果当前和已经超过目标和，则直接返回
if (sum > target) {
return;
}
// 如果当前和等于目标和，则将当前路径添加到结果中
if (sum == target) {
ret.add(new ArrayList<>(path));
return;
}
// 从当前起始索引开始，遍历所有候选数字
for (int i = startIndex; i < candidates.length; i++) {
// 由于数组已经排序，如果当前数字大于目标和减去当前和，可以直接剪枝
if (sum + candidates[i] > target) {
break;
}
// 将当前数字添加到路径中，并更新当前和
path.add(candidates[i]);
sum += candidates[i];
// 递归调用，搜索下一个数字，注意这里的起始索引是i，而不是i+1，以允许重复使用同一个数字
Demo(candidates, target, i, sum);
// 回溯，移除最后一个数字，恢复当前和
path.remove(path.size() - 1);
sum -= candidates[i];
}
}
}组合总和II
有重复元素数组中，处理同一个数组，宽度中不可重复选取已经使用过的元素，包括相同的元素
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
// 用于存储所有可能的组合
List<List<Integer>> ret = new ArrayList<>();
// 当前的组合
List<Integer> path = new ArrayList<>();
// 用于标记数组中的元素是否已经被使用
boolean used[];
/**
* 组合总和II问题的解法
* @param candidates 候选数字数组
* @param target 目标总和
* @return 返回所有可能的组合列表
*/
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length]; // 初始化使用标记数组
Arrays.sort(candidates); // 对候选数组进行排序，以便进行剪枝操作
// 如果候选数组为空或者为null，直接返回结果
if(candidates == null || candidates.length == 0){
return ret;
}
// 调用递归函数开始求解
Demo(candidates, target, 0, 0);
return ret; // 返回所有可能的组合
}
/**
* 递归函数，用于求解组合总和II问题
* @param candidates 候选数字数组
* @param target 目标总和
* @param startIndex 当前的起始索引
* @param sum 当前的总和
*/
void Demo(int[] candidates, int target, int startIndex, int sum){
// 如果当前总和已经超过目标总和，直接返回
if(sum > target){
return;
}
// 如果当前总和等于目标总和，将当前路径添加到结果中，并返回
if(sum == target){
ret.add(new ArrayList<>(path)); // 添加当前路径的副本到结果中
return;
}
// 从startIndex开始遍历候选数组
for(int i = startIndex; i < candidates.length; i++){
// 跳过重复的元素，以避免产生相同的组合
if(i > 0 && used[i - 1] == false && candidates[i] == candidates[i - 1]){
continue;
}
// 将当前元素加入到当前路径，并标记为已使用
sum += candidates[i];
path.add(candidates[i]);
used[i] = true;
// 递归调用Demo函数，以当前元素为起点，继续寻找可能的组合
Demo(candidates, target, i + 1, sum);
// 回溯，移除当前元素，以便尝试下一个元素
sum -= candidates[i];
path.remove(path.size() - 1);
used[i] = false;
}
}
}子集
无重复元素数组中，处理同一个数组，深度中不可重复选取已经使用过的元素
import java.util.ArrayList;
import java.util.List;
class Solution {
// 用于存储当前子集的路径
List<Integer> path = new ArrayList<>();
// 用于存储所有可能的子集
List<List<Integer>> ret = new ArrayList<>();
/**
* 生成给定数组的所有子集
* @param nums 输入的整数数组
* @return 包含所有子集的列表
*/
public List<List<Integer>> subsets(int[] nums) {
// 如果数组为空或为null，直接返回空的子集列表
if (nums == null || nums.length == 0) {
return ret;
}
// 调用递归函数生成所有子集
Demo(nums, 0);
// 返回包含所有子集的列表
return ret;
}
/**
* 递归函数，用于生成所有子集
* @param nums 输入的整数数组
* @param startIndex 当前递归的起始索引
*/
void Demo(int nums[], int startIndex) {
// 将当前路径添加到结果列表中
ret.add(new ArrayList<>(path));
// 遍历数组，从startIndex开始
for (int i = startIndex; i < nums.length; i++) {
// 将当前元素添加到路径中
path.add(nums[i]);
// 递归调用，从当前元素的下一个位置开始
Demo(nums, i + 1);
// 回溯，从路径中移除最后一个元素
path.remove(path.size() - 1);
}
}
}子集II
有重复元素数组中，处理同一个数组，宽度中不可重复选取已经使用过的元素，包括相同的元素
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
// 用于存储当前子集的路径
List<Integer> path = new ArrayList<>();
// 用于存储所有可能的子集
List<List<Integer>> ret = new ArrayList<>();
// 用于标记数组中的元素是否已经被使用过
boolean[] used;
/**
* 生成给定数组的所有子集，包括重复元素
* @param nums 输入的整数数组
* @return 包含所有子集的列表
*/
public List<List<Integer>> subsetsWithDup(int[] nums) {
// 初始化used数组，长度与输入数组相同
used = new boolean[nums.length];
// 对输入数组进行排序，以便更容易处理重复元素
Arrays.sort(nums);
// 调用递归函数生成所有子集
Demo(nums, 0);
// 返回包含所有子集的列表
return ret;
}
/**
* 递归函数，用于生成所有子集
* @param nums 输入的整数数组
* @param startIndex 当前递归的起始索引
*/
void Demo(int[] nums, int startIndex) {
// 将当前路径添加到结果列表中
ret.add(new ArrayList<>(path));
// 遍历数组，从startIndex开始
for (int i = startIndex; i < nums.length; i++) {
// 如果当前元素与前一个元素相同，并且前一个元素没有被使用过，则跳过当前元素
// 这避免了重复的子集
if (i > 0 && used[i - 1] == false && nums[i] == nums[i - 1]) {
continue;
}
// 将当前元素添加到路径中
path.add(nums[i]);
// 标记当前元素为已使用
used[i] = true;
// 递归调用，从当前元素的下一个位置开始
Demo(nums, i + 1);
// 回溯，从路径中移除最后一个元素
path.remove(path.size() - 1);
// 重置used数组，以便在下一次递归调用时重新考虑当前元素
used[i] = false;
}
}
}递增子序列(难）
有重复元素数组中，处理同一个数组，宽度中不可重复选取已经使用过的元素，包括相同的元素，而且不能排序。
用hashset去重，还有注意hashset的用法，每层都创建新的。hashset对每一层负责。
class Solution {
// 用于存储所有找到的连续子序列
List<List<Integer>> ret = new ArrayList<>();
// 用于存储当前正在构建的子序列
List<Integer> path = new ArrayList<>();
// 主方法，接收一个整数数组nums，并返回所有连续子序列
public List<List<Integer>> findSubsequences(int[] nums) {
// 如果数组为空或为null，直接返回空结果
if(nums.length == 0 || nums == null){
return ret;
}
// 调用递归方法，从数组的第0个元素开始构建子序列
Demo(nums, 0);
// 返回所有找到的子序列
return ret;
}
// 递归方法，用于构建连续子序列
void Demo(int[] nums, int startIndex){
// 如果当前路径长度大于1（至少有两个元素），则将其添加到结果集中
if(path.size() > 1){
ret.add(new ArrayList<>(path));
}
// 使用HashSet来存储已经访问过的元素，避免重复
HashSet<Integer> hashset = new HashSet<>();
// 从startIndex开始遍历数组
for(int i = startIndex ; i < nums.length ; i++){
// 如果当前元素已经访问过，或者当前元素小于路径中最后一个元素（保证递增），则跳过
if(hashset.contains(nums[i]) || !path.isEmpty() && path.get(path.size() - 1) > nums[i]){
continue;
}
// 将当前元素添加到路径和HashSet中
path.add(nums[i]);
hashset.add(nums[i]);
// 递归调用Demo方法，从下一个元素开始构建子序列
Demo(nums, i + 1);
// 回溯，移除路径中的最后一个元素，尝试其他可能的子序列
path.remove(path.size() - 1);
}
}
}排列
排列问题，去重是去深度的重，而不是宽度的重。深度是因为同一个排列能使用过已经使用过的元素。去重使用used的boolean数组，注意和组合问题使用的区别，就是深度去重used参数的设置问题。
全排列
这里需要在深度上去重
import java.util.ArrayList;
import java.util.List;
class Solution {
// 用于存储所有排列的结果
List<List<Integer>> ret = new ArrayList<>();
// 用于存储当前的排列路径
List<Integer> path = new ArrayList<>();
// 用于标记数组中的元素是否已经被使用过
boolean used[];
public List<List<Integer>> permute(int[] nums) {
// 初始化标记数组，长度与输入数组相同
used = new boolean[nums.length];
// 调用递归函数开始排列
Demo(nums);
// 返回所有排列的结果
return ret;
}
// 递归函数，用于生成排列
void Demo(int nums[]){
// 如果当前路径的长度等于输入数组的长度，说明找到了一个完整的排列
if(path.size() == nums.length){
// 将当前路径添加到结果集中
ret.add(new ArrayList<>(path));
return;
}
// 遍历输入数组中的每个元素
for(int i = 0; i < nums.length; i++){
// 如果该元素已经被使用过，则跳过
if(used[i] == true){
continue;
}
// 将当前元素添加到路径中
path.add(nums[i]);
// 标记该元素为已使用
used[i] = true;
// 递归调用Demo函数，尝试生成下一个元素的排列
Demo(nums);
// 回溯，将当前元素从路径中移除，并将标记重置为未使用
used[i] = false;
path.remove(path.size() - 1); // 优化：直接移除最后一个元素
}
}
}全排列 II
要对层去重，也要对深度去重，注意used的用法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
// 用于存储当前排列的路径
List<Integer> path = new ArrayList<>();
// 用于存储所有唯一的排列
List<List<Integer>> ret = new ArrayList<>();
// 用于标记数组中每个数字是否已经被使用过
boolean used[];
/**
* 生成数组nums的所有唯一排列。
* @param nums 输入的整数数组
* @return 包含所有唯一排列的列表
*/
public List<List<Integer>> permuteUnique(int[] nums) {
// 初始化used数组，长度与nums相同，初始值都为false
used = new boolean[nums.length];
// 对输入数组进行排序，以便后续处理重复数字
Arrays.sort(nums);
// 开始递归生成排列
Demo(nums);
// 返回所有唯一排列的列表
return ret;
}
/**
* 递归函数，用于生成排列。
* @param nums 输入的整数数组
*/
void Demo(int[] nums) {
// 如果当前路径的长度等于nums的长度，说明找到了一个完整的排列
if (nums.length == path.size()) {
// 将当前路径添加到结果列表中
ret.add(new ArrayList<>(path));
return;
}
// 遍历nums中的每个数字
for (int i = 0; i < nums.length; i++) {
// 如果当前数字与前一个数字相同，并且前一个数字没有被使用过，则跳过当前数字
if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
continue;
}
// 如果当前数字已经被使用过，则跳过
if (used[i]) {
continue;
}
// 将当前数字添加到路径中
path.add(nums[i]);
// 标记当前数字为已使用
used[i] = true;
// 递归调用Demo，生成下一个数字的排列
Demo(nums);
// 回溯，将当前数字从路径中移除，并将状态标记为未使用
used[i] = false;
path.remove(path.size() - 1);
}
}
}其他类型
复原IP地址（难）
有重复元素数组中，处理同一个数组，宽度中不可重复选取已经使用过的元素，不包括相同的元素，而且不能排序。
class Solution {
// 用于存储所有可能的IPv4地址
List<String> ret = new ArrayList<>();
// 主方法，接收一个字符串s，表示一个可能的IP地址序列
public List<String> restoreIpAddresses(String s) {
// 从字符串的开始位置（0）和计数0开始递归
Demo(s, 0, 0);
// 返回所有可能的IPv4地址
return ret;
}
// 递归方法，用于找出所有可能的IPv4地址
void Demo(String s, int startIndex, int count) {
// 如果已经找到了三段，检查剩下的部分是否构成一个有效的IP段
if(count == 3){
// 检查从当前起始位置到字符串末尾是否构成一个有效的IP段
if(isVaild(s, startIndex, s.length() - 1)){
// 如果有效，将这个IP地址添加到结果集中
ret.add(s);
return;
}
}
// 遍历字符串，尝试找出所有可能的IP段
for(int i = startIndex ; i < s.length() ; i++){
// 检查从当前起始位置到i位置是否构成一个有效的IP段
if(isVaild(s, startIndex, i)){
// 如果有效，将其添加到当前IP地址中，并尝试添加下一段
s = s.substring(0, i + 1) + "." + s.substring(i + 1);
count++;
// 递归调用Demo方法，尝试找出下一段
Demo(s, i + 1, count);
// 回溯，移除最后添加的段，尝试其他可能的段
s = s.substring(0, i + 1) + s.substring(i + 2);
count--;
}
}
}
// 辅助方法，用于检查一个字符串是否构成一个有效的IP段
boolean isVaild(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++){
// 如果字符不是数字，那么这个段是无效的
if(s.charAt(i) > '9' || s.charAt(i) < '0'){
return false;
}
// 将字符转换为数字，并加到整数中
int temp = s.charAt(i) - '0';
num = num * 10 + temp;
// 如果整数超过255，那么这个段是无效的
if(num > 255){
return false;
}
}
// 如果通过了所有检查，那么这个段是有效的
return true;
}
}分割回文串
这里是分割问题，不是组合问题。注意stringbuilder的使用。
有重复元素数组中，处理同一个数组，深度中不可重复选取已经使用过的元素，不包括相同的元素
class Solution {
// 用于存储当前的回文子串路径
List<String> path = new ArrayList<>();
// 用于存储所有可能的回文子串组合
List<List<String>> ret = new ArrayList<>();
// 主方法，接收一个字符串s，返回所有可能的回文子串组合
public List<List<String>> partition(String s) {
// 如果字符串为空或者长度为0，直接返回结果列表
if(s == null || s.length() == 0){
return ret;
}
// 从字符串的开始位置（索引0）开始递归寻找回文子串
Demo(s, 0, new StringBuilder());
// 返回所有找到的回文子串组合
return ret;
}
// 递归方法，用于深度优先搜索所有可能的回文子串组合
void Demo(String s, int startIndex, StringBuilder sb){
// 如果当前索引等于字符串的长度，说明找到了一个完整的回文子串路径
if(startIndex == s.length()){
// 将当前路径添加到结果列表中
ret.add(new ArrayList<>(path));
return;
}
// 遍历字符串，从当前索引开始，尝试每一种可能的子串
for(int i = startIndex ; i < s.length(); i++){
// 将当前字符添加到StringBuilder中，构建子串
sb.append(s.charAt(i));
// 判断当前构建的子串是否为回文
if(isHuiWenChuan(sb)){
// 如果是回文子串，则将其添加到当前路径中，并递归搜索下一种组合
path.add(sb.toString());
// 递归调用Demo方法，索引加1，因为当前子串已经确定为回文
Demo(s, i + 1, new StringBuilder());
// 回溯，从当前路径中移除最后一个子串，以便尝试下一种组合
path.remove(path.size() - 1);
}
}
}
// 判断一个字符串是否为回文
boolean isHuiWenChuan(StringBuilder s){
// 初始化左右两个指针，分别指向字符串的开始和结束位置
int left = 0;
int right = s.length() - 1;
// 使用双指针方法从两端向中间遍历，比较字符是否相等
while(left < right){
// 如果左右指针所指的字符不相等，则该字符串不是回文
if(s.charAt(left) != s.charAt(right)){
return false;
}
// 移动指针，继续比较下一对字符
left++;
right--;
}
// 如果所有字符都相等，说明该字符串是回文
return true;
}
}二维数组操作
N皇后（难）
class Solution {
// 用于存储所有可能的解决方案
List<List<String>> ret = new ArrayList<>();
// 主函数，接收棋盘大小n，返回所有可能的解决方案
public List<List<String>> solveNQueens(int n) {
// 初始化棋盘，所有位置都是空的（用'.'表示）
List<String> map = new ArrayList<>();
StringBuilder sb = new StringBuilder();
// 构建棋盘的每一行
for (int i = 0; i < n; i++) {
sb.append(".");
}
// 将每一行添加到棋盘map中
for (int i = 0; i < n; i++) {
map.add(sb.toString());
}
// 从第一行开始递归放置皇后
Demo(n, map, 0);
return ret;
}
// 递归函数，用于在棋盘上放置皇后
void Demo(int n, List<String> map, int row) {
// 如果当前行数等于棋盘大小，说明已经放置完所有皇后，记录这个解决方案
if (row == n) {
ret.add(new ArrayList<>(map));
return;
}
// 尝试在当前行的每个位置放置皇后
for (int col = 0; col < n; col++) {
// 检查当前位置是否合法
if (isVaild(map, n, row, col)) {
// 将当前位置的字符从'.'改为'Q'，表示放置了皇后
char ch[] = map.get(row).toCharArray();
ch[col] = 'Q';
map.set(row, new String(ch));
// 递归地在下一行放置皇后
Demo(n, map, row + 1);
// 回溯，撤销当前位置的皇后放置
ch[col] = '.';
map.set(row, new String(ch));
}
}
}
// 检查在给定的行和列上放置皇后是否合法
boolean isVaild(List<String> map, int n, int row, int col) {
// 检查当前列是否有其他皇后
for (int i = 0; i < row; i++) {
if (map.get(i).charAt(col) == 'Q') {
return false;
}
}
// 检查左上角方向是否有其他皇后
for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
if (map.get(i).charAt(j) == 'Q') {
return false;
}
}
// 检查右上角方向是否有其他皇后
for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
if (map.get(i).charAt(j) == 'Q') {
return false;
}
}
// 如果所有检查都通过，说明当前位置可以放置皇后
return true;
}
}解数独（难）
class Solution {
/**
* 主要的解决数独问题的方法。
* 这个方法接收一个字符类型的二维数组作为数独游戏的初始状态。
* @param board 一个9x9的字符数组，代表数独的初始状态。
*/
public void solveSudoku(char[][] board) {
Demo(board); // 调用递归方法来解决数独问题
}
/**
* 递归方法，用于尝试填充数独的空格。
* @param board 当前数独的状态。
* @return 如果数独成功解决返回true，否则返回false。
*/
boolean Demo(char[][] board) {
// 遍历数独的每个格子
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
// 如果当前格子已经有数字，则跳过
if (board[i][j] != '.') {
continue;
}
// 尝试在当前空格中填入1到9的数字
for (char k = '1'; k <= '9'; k++) {
// 检查当前数字是否可以填入当前格子
if (isVaild(board, i, j, k)) {
board[i][j] = k; // 将数字填入当前格子
// 递归调用Demo方法，尝试解决剩余的数独问题
if (Demo(board)) {
return true; // 如果成功解决，则返回true
}
// 如果填入当前数字后不能解决数独，则回溯，清空当前格子
board[i][j] = '.';
}
}
// 如果尝试了所有数字都不能解决数独，则返回false
return false;
}
}
// 如果遍历完所有格子，数独已经解决，则返回true
return true;
}
/**
* 检查在给定的行和列上是否可以填入给定的数字。
* @param board 当前数独的状态。
* @param row 要检查的行。
* @param col 要检查的列。
* @param val 要检查的数字。
* @return 如果可以填入返回true，否则返回false。
*/
boolean isVaild(char[][] board, int row, int col, char 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;
}
}
// 计算当前格子所在的3x3子网格的起始行和列
int localRow = (row / 3) * 3;
int localCol = (col / 3) * 3;
// 检查3x3子网格中是否有相同的数字
for (int i = localRow; i < localRow + 3; i++) {
for (int j = localCol; j < localCol + 3; j++) {
if (board[i][j] == val) {
return false;
}
}
}
// 如果检查通过，则可以填入数字
return true;
}
}本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！
转载请注明出处： 免费源码网-免费的源码资源网站 » 数据结构-回溯笔记
发表评论 取消回复