回溯算法

回溯的核心概念

回溯本质上是一种深度优先搜索，它通过逐步构建解决方案来探索所有可能的解决方案，并在确定部分解决方案无法扩展为有效解决方案时放弃该部分解决方案。

来源：src/main/java/com/thealgorithms/backtracking/ArrayCombination.java41-53 src/main/java/com/thealgorithms/backtracking/Combination.java49-66 src/main/java/com/thealgorithms/backtracking/Permutation.java34-43

回溯实现概述

该仓库包含多个经典回溯算法实现

来源：仓库目录结构和文件分析

组合生成

ArrayCombination

ArrayCombination 类使用回溯法生成从 0 到 n-1 的指定长度 k 的所有可能整数组合。

主要功能

时间复杂度：O(n choose k)
按字典序生成组合
通过剪枝高效处理大型组合空间
当当前大小加上剩余元素少于 k 时，执行早期回溯

来源：src/main/java/com/thealgorithms/backtracking/ArrayCombination.java

Combination

Combination 类提供了一种更通用的方法，用于从任何数组类型中生成指定长度的组合，并使用 TreeSet 来保持顺序。

主要实现细节

通过类型参数 <T> 支持通用数组类型
在生成组合之前对输入数组进行排序
将组合作为 TreeSet<T> 对象的列表返回
对组合长度为 0 的特殊情况处理

来源：src/main/java/com/thealgorithms/backtracking/Combination.java

排列生成

Permutation 类实现了回溯法，用于生成给定数组的所有可能排序（排列）。

实现亮点

采用基于交换的方法提高效率（避免辅助数据结构）
时间复杂度：O(n!)
对于长度为 n 的数组，最终结果包含 n! 种排列
通用实现适用于任何数组类型

来源：src/main/java/com/thealgorithms/backtracking/Permutation.java

迷宫求解

MazeRecursion 类演示了使用回溯法和不同移动策略求解迷宫。

实现细节

迷宫表示为二维整数数组，其中
- 0: 未访问/有效路径
- 1: 墙/障碍
- 2: 有效路径/已访问
- 3: 死胡同
实现了两种移动策略
- setWay: 下 → 右 → 上 → 左
- setWay2: 上 → 右 → 下 → 左
目标位置固定在坐标 (6,5)

来源：src/main/java/com/thealgorithms/backtracking/MazeRecursion.java

洪水填充算法

FloodFill 类实现了经典的洪水填充算法，该算法常用于图像处理和图形学。

主要功能

递归地用新颜色填充连通区域
支持正交（四向）和对角线（八向）连接
高效的边界和有效性检查
应用包括油漆桶工具和连通分量标记

来源：src/main/java/com/thealgorithms/backtracking/FloodFill.java

N皇后问题

NQueens 类解决了经典的N皇后问题：在N×N的棋盘上放置N个皇后，使得任意两个皇后都不能相互攻击。

实现细节

棋盘高效地表示为一维数组，其中 columns[i] 是第 i 列皇后的行位置
安全检查考虑了行冲突和对角线冲突
返回所有可能的有效布局
时间复杂度：O(N!)，但通过约束条件进行了显著优化

来源：src/main/java/com/thealgorithms/backtracking/NQueens.java

图路径查找

AllPathsFromSourceToTarget 类查找有向图中从源到目标的所有可能路径。

实现亮点

图使用邻接表表示
跟踪已访问顶点以避免循环
将所有路径作为顶点序列列表返回
在遍历过程中标记和取消标记顶点，以允许在不同路径中重复使用

来源：src/main/java/com/thealgorithms/backtracking/AllPathsFromSourceToTarget.java

回溯实现中的常见模式

该仓库的回溯实现共享了多种常见模式

组件	描述	示例
状态表示	当前部分解的表示方式	`Combination` 中的列表，`Permutation` 中的数组，`MazeRecursion` 中的二维数组
候选选择	如何为解决方案选择下一个元素	对数组元素的循环遍历，迷宫中的方向，`NQueens` 中的行
约束验证	检查当前状态是否有效	`Combination` 中的长度检查，`NQueens` 中的攻击检查
目标识别	判断是否找到完整解决方案	组合长度检查，在迷宫中达到目标，放置所有皇后
回溯机制	算法如何撤销选择	移除元素，交换回，标记/取消标记

来源：所有回溯实现文件

性能考量

回溯算法通常具有指数时间复杂度，但采用了多种优化技术

早期剪枝 - ArrayCombination 在剩余元素不足时停止
状态最小化 - NQueens 使用紧凑的一维数组表示
约束传播 - 在递归调用前检查有效性
高效状态跟踪 - 使用布尔数组表示已访问状态

来源：src/main/java/com/thealgorithms/backtracking/ArrayCombination.java49-50 src/main/java/com/thealgorithms/backtracking/NQueens.java102-108

与其他算法类别的关系

本仓库中的回溯算法与以下内容相关

来源：仓库分析和算法分类

总之，本仓库中的回溯实现展示了该算法技术在不同问题领域（从组合生成到路径查找和约束满足问题）的多功能性。