回溯
更新: 9/16/2025 字数: 0 字 时长: 0 分钟
全排列
java
/**
* <p>此方法解决“全排列”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：全排列问题是一个典型的组合搜索问题。我们可以通过深度优先搜索 (DFS) 的方式，
* 在每一步尝试将一个未使用的数字添加到当前排列中。当排列的长度达到原始数组的长度时，
* 就找到了一个完整的排列，将其加入结果集。之后，通过“回溯”操作（撤销之前的选择），
* 探索其他可能的路径。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code permute(nums)}：</strong>
* <ul>
* <li>{@code List<List<Integer>> result = new ArrayList<>();}：用于存储所有找到的全排列。</li>
* <li>{@code List<Integer> path = new ArrayList<>();}：用于存储当前正在构建的排列。</li>
* <li>{@code boolean[] used = new boolean[nums.length];}：一个布尔数组，用于标记 {@code nums} 数组中对应位置的元素是否已经在当前 {@code path} 中被使用过。初始全部为 {@code false}。</li>
* <li>调用辅助的回溯函数 {@code backtrack(nums, path, used, result)}。</li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(nums, path, used, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code nums}: 原始整数数组。</li>
* <li>{@code path}: 当前正在构建的排列。</li>
* <li>{@code used}: 标记 {@code nums} 中元素是否已使用的布尔数组。</li>
* <li>{@code result}: 存储所有完整排列的列表。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Case)：</strong>
* <ul>
* <li>{@code if (path.size() == nums.length)}：如果当前 {@code path} 的长度等于原始数组 {@code nums} 的长度，说明已经构建了一个完整的排列。
* <ul>
* <li>{@code result.add(new ArrayList<>(path));}：将当前 {@code path} 的一个<strong>副本</strong>添加到 {@code result} 中。
* <strong>注意：</strong> 必须是副本，因为 {@code path} 在后续的回溯过程中会被修改。</li>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归选择与探索：</strong>
* <ul>
* <li>{@code for (int i = 0; i < nums.length; i++)}：遍历原始数组 {@code nums} 中的所有元素。
* <ul>
* <li>{@code if (!used[i])}：如果 {@code nums[i]} 还没有被使用过 (即 {@code used[i]} 为 {@code false})：
* <ul>
* <li><strong>选择 (Choose)：</strong>
* <ul>
* <li>{@code path.add(nums[i]);}：将 {@code nums[i]} 加入当前排列。</li>
* <li>{@code used[i] = true;}：标记 {@code nums[i]} 为已使用。</li>
* </ul>
* </li>
* <li><strong>探索 (Explore)：</strong>
* <ul>
* <li>{@code backtrack(nums, path, used, result);}：递归调用，继续构建排列的下一个位置。</li>
* </ul>
* </li>
* <li><strong>撤销 (Unchoose/Backtrack)：</strong> 这是回溯的核心。当{@code backtrack}函数返回时，表示以当前选择{@code nums[i]}开头的路径已经探索完毕（或者已经找到了所有排列）。为了探索其他分支，需要撤销之前的选择，恢复到上一个状态。
* <ul>
* <li>{@code used[i] = false;}：将 {@code nums[i]} 的使用标记解除，使其在其他路径中可以被选择。</li>
* <li>{@code path.removeLast();}：将 {@code nums[i]} 从当前排列中移除，尝试下一个可能的选择。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N * N!)}。
* <ul>
* <li>其中 {@code N} 是数组 {@code nums} 的长度。</li>
* <li>生成 {@code N} 个数字的全排列有 {@code N!} 种。</li>
* <li>对于每一种排列，我们将其添加到结果列表中，这个操作需要 {@code O(N)} 的时间（复制 {@code path} 到 {@code ArrayList}）。</li>
* <li>因此，总时间复杂度是 {@code O(N * N!)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>{@code path} 列表的深度（即递归栈的深度）最大为 {@code N}。</li>
* <li>{@code used} 数组占用 {@code O(N)} 空间。</li>
* <li>{@code result} 列表存储了 {@code N!} 个排列，每个排列长度为 {@code N}。所以，如果把 {@code result} 算作额外空间的话，是 {@code O(N * N!)}。
* 但在多数算法题的语境中，输出列表不计入空间复杂度，或者只计入存储单个排列的空间。这里的 {@code O(N)} 指的是递归栈和辅助 {@code used} 数组的空间。</li>
* </ul>
* </li>
* </ul>
*/
public List<List<Integer>> permute(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 存储所有找到的全排列
List<Integer> path = new ArrayList<>(); // 存储当前正在构建的排列
boolean[] used = new boolean[nums.length]; // 标记每个数字是否已在当前排列中使用
// 调用回溯辅助函数
backtrack(nums, path, used, result);
return result;
}
/**
* 回溯辅助函数，用于生成全排列。
*
* @param nums 原始数组
* @param path 当前正在构建的排列
* @param used 布尔数组，标记 nums 中元素是否已使用
* @param result 存储所有完整排列的列表
*/
private void backtrack(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
// 递归终止条件：如果当前路径的长度等于原始数组的长度，说明已构建一个完整的排列
if (path.size() == nums.length) {
// 将当前路径的一个副本添加到结果列表中
// 必须是副本，因为 path 在后续回溯中会被修改
result.add(new ArrayList<>(path));
return; // 终止当前递归分支
}
// 遍历所有数字，尝试将其加入当前排列
for (int i = 0; i < nums.length; i++) {
// 如果 nums[i] 还没有被使用过
if (!used[i]) {
// 1. 选择：将 nums[i] 加入当前排列
path.add(nums[i]);
used[i] = true; // 标记 nums[i] 为已使用
// 2. 探索：递归调用，继续构建下一个位置
backtrack(nums, path, used, result);
// 3. 撤销：回溯，撤销 nums[i] 的使用标记，并从路径中移除
// 恢复到上一个状态，以便尝试其他选择
used[i] = false;
path.removeLast();
}
}
}子集
java
/**
* <p>此方法解决“子集”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：子集问题是典型的组合搜索问题。对于数组中的每个元素，我们有两个选择：
* 要么将其包含在当前子集中，要么不包含。通过递归地探索这两种可能性，我们可以生成所有子集。</p>
* <p>为了避免生成重复的子集（例如 {@code [1,2]} 和 {@code [2,1]} 代表同一个子集），
* 我们通过一个 {@code startIndex} 参数来控制在每层递归中从哪个位置开始选择元素，
* 确保每个元素只在特定位置被考虑一次，从而保证生成的子集是按照非递减顺序（或只是不含重复元素）的。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code subsets(nums)}：</strong>
* <ul>
* <li>{@code List<List<Integer>> result = new ArrayList<>();}：用于存储所有找到的子集。</li>
* <li>{@code List<Integer> path = new ArrayList<>();}：用于存储当前正在构建的子集。</li>
* <li>调用辅助的回溯函数 {@code backtrack(nums, 0, path, result)}。初始 {@code startIndex} 为 {@code 0}。</li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(nums, startIndex, path, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code nums}: 原始整数数组。</li>
* <li>{@code startIndex}: 当前递归层级中，从 {@code nums} 的哪个索引开始考虑选择元素。</li>
* <li>{@code path}: 当前正在构建的子集。</li>
* <li>{@code result}: 存储所有子集的列表。</li>
* </ul>
* </li>
* <li><strong>递归入口 (收集当前子集)：</strong>
* <ul>
* <li>{@code result.add(new ArrayList<>(path));}：
* <strong>重要步骤！</strong> 在每层递归的开始，将当前 {@code path} 的一个<strong>副本</strong>添加到 {@code result} 中。
* 包括空集，以及只包含部分元素的子集。
* 例如，当 {@code path} 为 {@code [1]} 时，它是一个有效的子集，应该被收集。</li>
* </ul>
* </li>
* <li><strong>递归选择与探索：</strong>
* <ul>
* <li>{@code for (int i = startIndex; i < nums.length; i++)}：
* 从 {@code startIndex} 开始遍历 {@code nums} 数组。
* 这样可以确保每个元素只会被考虑一次，避免重复子集。
* （例如，{@code [1,2]} 和 {@code [2,1]} 都会被生成，
* 但由于我们的循环从 {@code startIndex} 开始，{@code [2,1]} 这种情况不会出现）。
* </li>
* <li><strong>选择 (Choose)：</strong>
* <ul>
* <li>{@code path.add(nums[i]);}：将 {@code nums[i]} 加入当前子集。</li>
* </ul>
* </li>
* <li><strong>探索 (Explore)：</strong>
* <ul>
* <li>{@code backtrack(nums, i + 1, path, result);}：递归调用，从 {@code i + 1} 开始考虑下一个元素。
* <strong>注意：</strong> 这里的 {@code startIndex} 变为 {@code i + 1}，确保后续的选择不会重复选择当前元素或其之前的元素。</li>
* </ul>
* </li>
* <li><strong>撤销 (Unchoose/Backtrack)：</strong>
* <ul>
* <li>{@code path.removeLast();}：回溯，将 {@code nums[i]} 从当前 {@code path} 中移除，
* 以便探索不包含 {@code nums[i]} 的其他分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N * 2^N)}。
* <ul>
* <li>{@code N} 是数组 {@code nums} 的长度。</li>
* <li>总共有 {@code 2^N} 个子集。</li>
* <li>对于每个子集，我们将其添加到结果列表中，这个操作需要 {@code O(N)} 的时间（复制 {@code path} 到 {@code ArrayList}）。</li>
* <li>因此，总时间复杂度是 {@code O(N * 2^N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>{@code path} 列表的深度（即递归栈的深度）最大为 {@code N}。</li>
* <li>{@code result} 列表存储了 {@code 2^N} 个子集，每个子集长度平均为 {@code N/2}，最大为 {@code N}。
* 所以，如果把 {@code result} 算作输出空间，则是 {@code O(N * 2^N)}。这里的 {@code O(N)} 指的是递归栈和辅助 {@code path} 列表的空间。</li>
* </ul>
* </li>
* </ul>
*/
public List<List<Integer>> subsets(int[] nums) {
List<List<Integer>> result = new ArrayList<>(); // 存储所有子集
List<Integer> path = new ArrayList<>(); // 存储当前正在构建的子集
// 从索引 0 开始回溯
backtrack(nums, 0, path, result);
return result;
}
/**
* 回溯辅助函数，用于生成子集。
*
* @param nums 原始数组
* @param startIndex 当前递归层级开始考虑 nums 数组的哪个索引
* @param path 当前正在构建的子集
* @param result 存储所有子集的列表
*/
private void backtrack(int[] nums, int startIndex, List<Integer> path, List<List<Integer>> result) {
// 1. 递归入口：将当前 path（代表一个子集）的副本添加到结果列表中
// 这一步是关键，因为空集也是一个子集，并且在每次递归深入时 path 都代表一个有效的子集
result.add(new ArrayList<>(path));
// 2. 递归选择与探索：从 startIndex 开始遍历，避免重复的子集
for (int i = startIndex; i < nums.length; i++) {
// 选择：将 nums[i] 加入当前子集
path.add(nums[i]);
// 探索：递归调用，从下一个元素 i + 1 开始考虑
backtrack(nums, i + 1, path, result);
// 撤销：回溯，将 nums[i] 从当前子集中移除，探索不包含 nums[i] 的分支
path.removeLast();
}
}电话号码的字母组合
java
/**
* <p>此方法解决“电话号码的字母组合”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：这是一个典型的组合问题。对于输入的每个数字，它都可以映射到一组字母。
* 我们需要从这些字母组中，为每个数字选择一个字母，然后将它们组合成一个字符串。
* 回溯算法通过深度优先搜索的方式，遍历所有可能的字母选择路径。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>映射字典：</strong>
* <ul>
* <li>定义一个 {@code String[] mapping} (或 {@code Map<Character, String>}) 来存储数字到字母的映射关系。
* 例如：{@code String[] mapping = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};}</li>
* </ul>
* </li>
* <li><strong>主函数 {@code letterCombinations(digits)}：</strong>
* <ul>
* <li>{@code List<String> result = new ArrayList<>();}：用于存储所有找到的字母组合。</li>
* <li><strong>边界条件处理：</strong> {@code if (digits == null || digits.isEmpty())}，直接返回空的 {@code result} 列表。</li>
* <li>{@code StringBuilder currentCombination = new StringBuilder();}：用于存储当前正在构建的字母组合。使用 {@code StringBuilder} 比 {@code String} 在字符串拼接操作上更高效。</li>
* <li>调用辅助的回溯函数 {@code backtrack(digits, 0, mapping, currentCombination, result)}。初始 {@code index} 为 {@code 0}。</li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(digits, index, mapping, currentCombination, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code digits}: 输入的数字字符串。</li>
* <li>{@code index}: 当前正在处理 {@code digits} 字符串中的哪个数字的索引。</li>
* <li>{@code mapping}: 数字到字母的映射表。</li>
* <li>{@code currentCombination}: 当前正在构建的字母组合。</li>
* <li>{@code result}: 存储所有完整组合的列表。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Case)：</strong>
* <ul>
* <li>{@code if (index == digits.length())}：如果 {@code index} 等于 {@code digits} 的长度，说明已经处理完所有数字，{@code currentCombination} 已形成一个完整的字母组合。
* <ul>
* <li>{@code result.add(currentCombination.toString());}：将当前组合添加到 {@code result} 中。</li>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归选择与探索：</strong>
* <ul>
* <li>{@code char digitChar = digits.charAt(index);}：获取当前要处理的数字字符。</li>
* <li>{@code String letters = mapping[digitChar - '0'];}：根据映射获取该数字对应的所有字母。
* （例如，{@code '2' - '0'} 得到整数 {@code 2}，然后用 {@code mapping[2]} 得到 {@code "abc"}）。</li>
* <li>{@code for (char letter : letters.toCharArray())}：遍历 {@code letters} 中的每个字母：
* <ul>
* <li><strong>选择 (Choose)：</strong>
* <ul>
* <li>{@code currentCombination.append(letter);}：将当前字母 {@code letter} 加入组合。</li>
* </ul>
* </li>
* <li><strong>探索 (Explore)：</strong>
* <ul>
* <li>{@code backtrack(digits, index + 1, mapping, currentCombination, result);}：递归调用，处理 {@code digits} 中的下一个数字。</li>
* </ul>
* </li>
* <li><strong>撤销 (Unchoose/Backtrack)：</strong>
* <ul>
* <li>{@code currentCombination.deleteCharAt(currentCombination.length() - 1);}：回溯，移除 {@code currentCombination} 中最后添加的字母。这使得我们可以尝试当前数字的其他字母选择。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(4^N * N)}。
* <ul>
* <li>其中 {@code N} 是输入字符串 {@code digits} 的长度。</li>
* <li>{@code 4} 是因为数字 {@code 7} 和 {@code 9} 对应了 4 个字母，这是每层递归分支数量的最大值。</li>
* <li>最坏情况下，{@code N} 位数字的组合数量大约是 {@code 4^N}。</li>
* <li>对于每个组合，将其添加到结果列表需要 {@code O(N)} 的时间 (因为 {@code StringBuilder.toString()} 和 {@code ArrayList.add()})。</li>
* <li>因此，总时间复杂度是 {@code O(4^N * N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)} (不包括结果列表)。
* <ul>
* <li>递归栈的深度最大为 {@code N}。</li>
* <li>{@code currentCombination} 的长度也最大为 {@code N}。</li>
* <li>{@code mapping} 数组是常量空间。</li>
* <li>如果将结果列表计算在内，则空间复杂度为 {@code O(4^N * N)}。</li>
* </ul>
* </li>
* </ul>
*/
// 数字到字母的映射表
private final String[] mapping = {
"", // 0
"", // 1
"abc", // 2
"def", // 3
"ghi", // 4
"jkl", // 5
"mno", // 6
"pqrs", // 7
"tuv", // 8
"wxyz" // 9
};
public List<String> letterCombinations(String digits) {
List<String> result = new ArrayList<>(); // 存储所有找到的字母组合
// 边界条件处理：如果输入为空或 null，返回空列表
if (digits == null || digits.isEmpty()) {
return result;
}
StringBuilder currentCombination = new StringBuilder(); // 存储当前正在构建的字母组合
// 调用回溯辅助函数
backtrack(digits, 0, currentCombination, result);
return result;
}
/**
* 回溯辅助函数，用于生成字母组合。
*
* @param digits 输入的数字字符串
* @param index 当前正在处理 digits 字符串的哪个数字的索引
* @param currentCombination 当前正在构建的字母组合
* @param result 存储所有完整组合的列表
*/
private void backtrack(String digits, int index,
StringBuilder currentCombination, List<String> result) {
// 递归终止条件：如果 index 等于 digits 的长度，说明已经处理完所有数字
if (index == digits.length()) {
// 将当前形成的组合添加到结果列表中
result.add(currentCombination.toString());
return; // 终止当前递归分支
}
// 获取当前要处理的数字字符
char digitChar = digits.charAt(index);
// 根据映射获取该数字对应的所有字母
String letters = mapping[digitChar - '0'];
// 遍历当前数字对应的所有字母
for (char letter : letters.toCharArray()) {
// 1. 选择：将当前字母加入组合
currentCombination.append(letter);
// 2. 探索：递归调用，处理下一个数字
backtrack(digits, index + 1, currentCombination, result);
// 3. 撤销：回溯，移除最后添加的字母，尝试当前数字的下一个字母选择
// 使用 deleteCharAt(length - 1) 比 setLength(length - 1) 更直观，虽然效果相同
currentCombination.deleteCharAt(currentCombination.length() - 1);
}
}组合总和
java
/**
* <p>此方法解决“组合总和”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：这是一个典型的组合问题，带有重复选取数字的特性。我们可以通过深度优先搜索 (DFS) 的方式，
* 不断尝试从 {@code candidates} 数组中选择数字，并累加它们的和。当和达到 {@code target} 时，
* 我们就找到一个有效的组合；当和超过 {@code target} 时，当前路径就不再有效，可以停止探索（剪枝）。</p>
* <p>为了避免生成重复的组合（例如 {@code [2,3]} 和 {@code [3,2]}），我们通过一个 {@code startIndex} 参数来控制
* 在每层递归中从 {@code candidates} 数组的哪个位置开始选择元素。
* 由于同一个数字可以被无限制重复选取，在选择 {@code candidates[i]} 之后，下一轮递归的 {@code startIndex}
* 仍然是 {@code i}，而不是 {@code i + 1}。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code combinationSum(candidates, target)}：</strong>
* <ul>
* <li>{@code List<List<Integer>> result = new ArrayList<>();}：用于存储所有找到的组合。</li>
* <li>{@code List<Integer> currentCombination = new ArrayList<>();}：用于存储当前正在构建的组合。</li>
* <li><strong>优化：</strong> {@code Arrays.sort(candidates);}：对 {@code candidates} 数组进行排序。
* <ul>
* <li>这有助于在回溯过程中进行<strong>剪枝</strong>操作：如果 {@code currentSum + candidates[i]} 已经大于 {@code target}，
* 那么由于数组已排序，后续的 {@code candidates} 元素也会更大，所以无需继续遍历，可以直接 {@code break} 当前循环。</li>
* <li>虽然不是强制性的，但排序通常是处理组合问题的良好实践。</li>
* </ul>
* </li>
* <li>调用辅助的回溯函数 {@code backtrack(candidates, target, 0, 0, currentCombination, result)}。
* <ul>
* <li>{@code target}: 目标和。</li>
* <li>{@code currentSum}: 当前组合的和。</li>
* <li>{@code startIndex}: 从 {@code candidates} 数组的索引 {@code 0} 开始。</li>
* </ul>
* </li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(candidates, target, currentSum, startIndex, currentCombination, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code candidates}: 原始整数数组。</li>
* <li>{@code target}: 目标和。</li>
* <li>{@code currentSum}: 当前组合的总和。</li>
* <li>{@code startIndex}: 当前递归层级中，从 {@code candidates} 的哪个索引开始考虑选择元素。</li>
* <li>{@code currentCombination}: 当前正在构建的组合。</li>
* <li>{@code result}: 存储所有完整组合的列表。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Case)：</strong>
* <ul>
* <li>{@code if (currentSum == target)}：如果当前组合的总和等于 {@code target}，说明找到了一个合法组合。
* <ul>
* <li>{@code result.add(new ArrayList<>(currentCombination));}：将当前 {@code currentCombination} 的一个<strong>副本</strong>添加到 {@code result} 中。必须是副本。</li>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* <li>{@code if (currentSum > target)}：如果当前组合的总和已经超过 {@code target}，无论再添加什么数字都会更大。当前路径无效，进行<strong>剪枝</strong>。
* <ul>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归选择与探索：</strong>
* <ul>
* <li>{@code for (int i = startIndex; i < candidates.length; i++)}：
* 从 {@code startIndex} 开始遍历 {@code candidates} 数组。
* {@code startIndex} 确保了不重复使用已经遍历过的元素（在相同层级），从而避免重复组合。
* </li>
* <li><strong>进一步剪枝 (基于排序)：</strong>
* <ul>
* <li>{@code if (currentSum + candidates[i] > target)}：如果当前和加上 {@code candidates[i]} 已经大于 {@code target}，
* 由于 {@code candidates} 数组已经排序，后面的元素只会更大，因此当前循环中再选择其他元素也没有意义。
* 直接 {@code break} 退出当前循环。</li>
* </ul>
* </li>
* <li><strong>选择 (Choose)：</strong>
* <ul>
* <li>{@code currentCombination.add(candidates[i]);}：将 {@code candidates[i]} 加入当前组合。</li>
* <li>{@code currentSum += candidates[i];}：更新当前总和。</li>
* </ul>
* </li>
* <li><strong>探索 (Explore)：</strong>
* <ul>
* <li>{@code backtrack(candidates, target, currentSum, i, currentCombination, result);}：递归调用。
* <strong>关键点：</strong> 这里的 {@code startIndex} 仍然是 {@code i}，而不是 {@code i + 1}，
* 因为题目允许<strong>同一个数字可以无限制重复选取</strong>。</li>
* </ul>
* </li>
* <li><strong>撤销 (Unchoose/Backtrack)：</strong>
* <ul>
* <li>{@code currentCombination.removeLast();}：回溯，将 {@code candidates[i]} 从当前组合中移除。</li>
* <li>{@code currentSum -= candidates[i];}：恢复总和，以便探索不包含 {@code candidates[i]} 的其他分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> 这是一个相对复杂的问题，其时间复杂度通常难以用简单的公式精确表达，因为它取决于剪枝的效率和 {@code target} 的大小。
* 一个宽松的上界是 {@code O(S * 2^N)} 或者 {@code O(N^(target/min_candidate))}。
* <ul>
* <li>{@code N} 是 {@code candidates} 数组的长度。</li>
* <li>{@code S} 是所有合法组合的数量（题目中保证 < 150）。</li>
* <li>在最坏情况下，如果没有有效的剪枝（例如 {@code candidates = [1,1,1...]}），它会非常接近 {@code N^target}。</li>
* <li>但是，由于有剪枝和 {@code startIndex} 的限制，并允许重复使用元素，每次递归调用的分支数是 {@code N - startIndex + 1}，层数最大是 {@code target / min(candidates)}。</li>
* <li>对于每个合法的组合，需要 {@code O(K)} 的时间添加到结果中，其中 {@code K} 是组合的长度。</li>
* <li>通常认为这种组合问题的回溯时间复杂度是指数级的。这里的分析会比较粗略，但实际运行效率会比无剪枝要好。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(target / min(candidates))}。
* <ul>
* <li>递归栈的深度最大为 {@code target / min(candidates)}（当 {@code candidates} 中最小元素为 1 时，深度可达 {@code target}）。</li>
* <li>{@code currentCombination} 列表的长度也最大为 {@code target / min(candidates)}。</li>
* <li>{@code result} 列表存储了所有组合。如果将其计入空间复杂度，则为 {@code O(S * K)}，其中 {@code S} 是组合数，{@code K} 是平均组合长度。这里的 {@code O(target / min(candidates))} 指的是递归栈和辅助 {@code currentCombination} 列表的空间。</li>
* </ul>
* </li>
* </ul>
*/
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> result = new ArrayList<>(); // 存储所有找到的组合
List<Integer> currentCombination = new ArrayList<>(); // 存储当前正在构建的组合
// 优化：对 candidates 数组进行排序。
// 这有助于在回溯过程中进行剪枝操作，提高效率。
Arrays.sort(candidates);
// 调用回溯辅助函数
// 参数：原始数组，目标和，当前总和，起始索引，当前组合，结果列表
backtrack(candidates, target, 0, 0, currentCombination, result);
return result;
}
/**
* 回溯辅助函数，用于生成组合总和。
*
* @param candidates 原始整数数组
* @param target 目标和
* @param currentSum 当前组合的总和
* @param startIndex 当前递归层级中，从 candidates 的哪个索引开始考虑选择元素
* @param currentCombination 当前正在构建的组合
* @param result 存储所有完整组合的列表
*/
private void backtrack(int[] candidates, int target, int currentSum,
int startIndex, List<Integer> currentCombination,
List<List<Integer>> result) {
// 递归终止条件 - 成功：如果当前组合的总和等于 target
if (currentSum == target) {
// 找到一个合法组合，将其副本添加到结果列表中
result.add(new ArrayList<>(currentCombination));
return; // 终止当前递归分支
}
// 递归终止条件 - 失败/剪枝：如果当前组合的总和已经超过 target
// 无论再添加什么数字都会更大，当前路径无效
if (currentSum > target) {
return; // 直接返回，进行剪枝
}
// 递归选择与探索：从 startIndex 开始遍历 candidates 数组
for (int i = startIndex; i < candidates.length; i++) {
// 进一步剪枝（基于数组已排序的优化）：
// 如果当前和加上 candidates[i] 已经大于 target，
// 那么由于数组已排序，后续的 candidates 元素只会更大，因此当前循环中
// 再选择其他元素也没有意义，可以直接 break 退出当前循环。
if (currentSum + candidates[i] > target) {
break;
}
// 1. 选择：将 candidates[i] 加入当前组合
currentCombination.add(candidates[i]);
currentSum += candidates[i]; // 更新当前总和
// 2. 探索：递归调用，处理下一个选择
// 关键点：startIndex 仍然是 i，而不是 i + 1。
// 因为同一个数字可以无限制重复选取。
backtrack(candidates, target, currentSum, i, currentCombination, result);
// 3. 撤销：回溯，将 candidates[i] 从当前组合中移除，并恢复总和
// 恢复到上一个状态，以便探索不包含 candidates[i] 的其他分支
currentCombination.removeLast();
currentSum -= candidates[i];
}
}括号生成
java
/**
* <p>此方法解决“括号生成”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：生成所有有效的括号组合是一个典型的组合搜索问题。我们可以通过深度优先搜索 (DFS) 的方式，
* 在每个步骤中尝试添加左括号或右括号。关键在于，在添加的过程中，需要实时检查当前组合的“有效性”，
* 以便进行剪枝（Pruning），避免探索无效的路径。</p>
*
* <h3>有效括号的两个核心规则：</h3>
* <ol>
* <li><strong>左括号数量不能超过 n。</strong></li>
* <li><strong>右括号数量不能超过左括号数量。</strong> (即，在任何时候，右括号的数量都不能多于左括号，否则就无效了)</li>
* <li>最终，左右括号数量都必须等于 {@code n}。</li>
* </ol>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code generateParenthesis(n)}：</strong>
* <ul>
* <li>{@code List<String> result = new ArrayList<>();}：用于存储所有找到的有效括号组合。</li>
* <li>{@code StringBuilder currentString = new StringBuilder();}：用于存储当前正在构建的括号字符串。使用 {@code StringBuilder} 比 {@code String} 在字符串拼接操作上更高效。</li>
* <li>调用辅助的回溯函数 {@code backtrack(n, 0, 0, currentString, result)}。
* <ul>
* <li>{@code n}: 目标括号对数。</li>
* <li>{@code openCount}: 当前已使用的左括号数量，初始为 {@code 0}。</li>
* <li>{@code closeCount}: 当前已使用的右括号数量，初始为 {@code 0}。</li>
* </ul>
* </li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(n, openCount, closeCount, currentString, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code n}: 总的括号对数。</li>
* <li>{@code openCount}: 当前已使用的左括号数量。</li>
* <li>{@code closeCount}: 当前已使用的右括号数量。</li>
* <li>{@code currentString}: 当前正在构建的括号字符串。</li>
* <li>{@code result}: 存储所有完整有效组合的列表。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Case)：</strong>
* <ul>
* <li>{@code if (currentString.length() == 2 * n)}：如果当前字符串的长度达到了 {@code 2 * n} （即 {@code n} 对括号的总长度），说明已经构建了一个完整的组合。
* <ul>
* <li>{@code result.add(currentString.toString());}：将当前组合添加到 {@code result} 中。</li>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归选择与探索（并进行剪枝）：</strong>
* <ul>
* <li><strong>尝试添加左括号：</strong>
* <ul>
* <li>{@code if (openCount < n)}：只有当已使用的左括号数量小于总共需要的 {@code n} 时，才能添加左括号。
* <ul>
* <li><strong>选择：</strong> {@code currentString.append('(');}</li>
* <li><strong>探索：</strong> {@code backtrack(n, openCount + 1, closeCount, currentString, result);}：递归调用，左括号数量加一。</li>
* <li><strong>撤销 (回溯)：</strong> {@code currentString.deleteCharAt(currentString.length() - 1);}：移除最后添加的左括号，以便探索其他分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>尝试添加右括号：</strong>
* <ul>
* <li>{@code if (closeCount < openCount)}：只有当已使用的右括号数量小于已使用的左括号数量时，才能添加右括号。这是确保有效性的关键条件。
* <ul>
* <li><strong>选择：</strong> {@code currentString.append(')');}</li>
* <li><strong>探索：</strong> {@code backtrack(n, openCount, closeCount + 1, currentString, result);}：递归调用，右括号数量加一。</li>
* <li><strong>撤销 (回溯)：</strong> {@code currentString.deleteCharAt(currentString.length() - 1);}：移除最后添加的右括号，以便探索其他分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(4^n / (n * sqrt(n)))}，这是卡特兰数 (Catalan Number) 的渐近复杂度。
* <ul>
* <li>{@code N} 是输入的 {@code n}，代表括号对数。</li>
* <li>生成所有有效括号组合的数量是第 {@code n} 个卡特兰数 {@code C_n = (2n)! / (n! * (n+1)!)}。</li>
* <li>每个组合的构建和复制操作需要 {@code O(2n)} 的时间。</li>
* <li>因此，总时间复杂度是 {@code O(C_n * n)}，用渐近形式表示为 {@code O(4^n / (n * sqrt(n)) * n)}，简化后依然是 {@code O(4^n / sqrt(n))}。</li>
* <li>这是一种指数级的时间复杂度，但由于大量的剪枝，它实际上比 {@code O(2^(2n))}（不剪枝的所有可能字符串）要好得多。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(n)}。
* <ul>
* <li>递归栈的深度最大为 {@code 2n}。</li>
* <li>{@code currentString} 的长度最大也为 {@code 2n}。</li>
* <li>如果将结果列表计算在内，则空间复杂度为 {@code O(C_n * n)}。这里的 {@code O(n)} 指的是递归栈和辅助 {@code currentString} 列表的空间。</li>
* </ul>
* </li>
* </ul>
*/
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>(); // 存储所有找到的有效括号组合
// StringBuilder 用于高效地构建字符串，在回溯时方便移除字符
StringBuilder currentString = new StringBuilder();
// 调用回溯辅助函数
// 参数：n（目标对数）, openCount（已使用左括号数）, closeCount（已使用右括号数）,
// currentString（当前组合）, result（结果列表）
backtrack(n, 0, 0, currentString, result);
return result;
}
/**
* 回溯辅助函数，用于生成所有有效的括号组合。
*
* @param n 总的括号对数
* @param openCount 当前已使用的左括号数量
* @param closeCount 当前已使用的右括号数量
* @param currentString 当前正在构建的括号字符串
* @param result 存储所有完整有效组合的列表
*/
private void backtrack(int n, int openCount, int closeCount,
StringBuilder currentString, List<String> result) {
// 递归终止条件：如果当前字符串的长度达到了 2 * n (即 n 对括号的总长度)
if (currentString.length() == 2 * n) {
// 找到一个完整的有效组合，将其添加到结果列表中
result.add(currentString.toString());
return; // 终止当前递归分支
}
// 尝试添加左括号：
// 只有当已使用的左括号数量小于总共需要的 n 时，才能添加左括号
if (openCount < n) {
// 1. 选择：添加左括号
currentString.append('(');
// 2. 探索：递归调用，左括号数量加一
backtrack(n, openCount + 1, closeCount, currentString, result);
// 3. 撤销：回溯，移除最后添加的左括号，以便探索其他分支
currentString.deleteCharAt(currentString.length() - 1);
}
// 尝试添加右括号：
// 只有当已使用的右括号数量小于已使用的左括号数量时，才能添加右括号。
// 这是确保有效性的关键条件。
if (closeCount < openCount) {
// 1. 选择：添加右括号
currentString.append(')');
// 2. 探索：递归调用，右括号数量加一
backtrack(n, openCount, closeCount + 1, currentString, result);
// 3. 撤销：回溯，移除最后添加的右括号，以便探索其他分支
currentString.deleteCharAt(currentString.length() - 1);
}
}单词搜索
java
/**
* <p>此方法解决“单词搜索”问题，采用经典的<strong>深度优先搜索（DFS）+ 回溯算法</strong>。</p>
* <p>核心思想：我们需要在二维网格中，从任意一个满足首字母条件的单元格开始，
* 沿着水平或垂直方向“搜索”目标单词的每个字母。
* 由于同一个单元格不能被重复使用，这要求我们在搜索路径时，
* 对已访问的单元格进行标记，并在回溯时撤销标记。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code exist(board, word)}：</strong>
* <ul>
* <li>首先处理边界情况：如果 {@code board} 为空或 {@code word} 为空，根据题目要求返回 {@code false} 或 {@code true}（通常 {@code word} 为空不算存在）。这里假设 {@code word} 不为空。</li>
* <li>获取网格的尺寸 {@code m} (行数) 和 {@code n} (列数)。</li>
* <li>外层循环：遍历 {@code board} 中的每一个单元格 {@code (i, j)}。
* <ul>
* <li>{@code for (int i = 0; i < m; i++)}</li>
* <li>{@code for (int j = 0; j < n; j++)}</li>
* <li><strong>作为起点尝试：</strong> {@code if (board[i][j] == word.charAt(0))}：
* 如果当前单元格的字符与 {@code word} 的第一个字符匹配，就以 {@code (i, j)} 为起点，开始一次深度优先搜索。
* 调用 {@code dfs(board, word, 0, i, j)}。如果返回 {@code true}，说明找到了单词，立即返回 {@code true}。</li>
* </ul>
* </li>
* <li>如果遍历完所有可能的起点都没有找到单词，最后返回 {@code false}。</li>
* </ul>
* </li>
* <li><strong>DFS 辅助函数 {@code dfs(board, word, index, r, c)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code board}: 字符网格。</li>
* <li>{@code word}: 目标单词。</li>
* <li>{@code index}: 当前正在匹配 {@code word} 的第 {@code index} 个字符。</li>
* <li>{@code r}: 当前单元格的行索引。</li>
* <li>{@code c}: 当前单元格的列索引。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Cases)：</strong>
* <ul>
* <li><strong>成功匹配：</strong> {@code if (index == word.length())}：如果 {@code index} 已经达到 {@code word} 的长度，说明 {@code word} 中的所有字符都已成功匹配，返回 {@code true}。</li>
* <li><strong>失败情况 (剪枝)：</strong>
* <ul>
* <li>{@code if (r < 0 || r >= board.length || c < 0 || c >= board[0].length)}：当前 {@code (r, c)} 越界。</li>
* <li>{@code if (board[r][c] != word.charAt(index))}：当前单元格的字符与 {@code word} 的目标字符不匹配。
* （这里的 {@code board[r][c]} 可能是原始字符，也可能是标记过的特殊字符，但特殊字符一定不匹配 {@code word} 中的字母）</li>
* </ul>
* <strong>以上任何一种情况，都直接返回 {@code false}。</strong>
* </li>
* </ul>
* </li>
* <li><strong>DFS 核心步骤：</strong>
* <ul>
* <li><strong>1. 标记当前单元格：</strong>
* <ul>
* <li>{@code char originalChar = board[r][c];}：保存当前单元格的原始字符。</li>
* <li>{@code board[r][c] = '#';}：将当前单元格的字符<strong>临时修改</strong>为一个特殊字符（例如 {@code #}），表示该单元格已被当前路径访问，以避免重复使用。
* 这是实现“同一个单元格内的字母不允许被重复使用”的关键。</li>
* </ul>
* </li>
* <li><strong>2. 向四个方向探索 (递归)：</strong>
* <ul>
* <li>{@code boolean found = false;}：初始化一个标志，用于记录是否在任意方向找到了单词。</li>
* <li>{@code found = dfs(board, word, index + 1, r + 1, c) || // 向下}</li>
* <li>{@code dfs(board, word, index + 1, r - 1, c) || // 向上}</li>
* <li>{@code dfs(board, word, index + 1, r, c + 1) || // 向右}</li>
* <li>{@code dfs(board, word, index + 1, r, c - 1); // 向左}</li>
* <li>如果任何一个方向的递归调用返回 {@code true}，则 {@code found} 为 {@code true}。</li>
* </ul>
* </li>
* <li><strong>3. 撤销标记 (回溯)：</strong>
* <ul>
* <li>无论是否找到单词，在当前 {@code dfs} 调用结束前，必须将 {@code board[r][c]} 恢复为其原始字符 {@code originalChar}。
* {@code board[r][c] = originalChar;}
* 这是回溯的关键，它允许其他潜在的路径在后续的搜索中重新使用这个单元格。</li>
* </ul>
* </li>
* <li><strong>4. 返回 {@code found}。</strong></li>
* </ul>
* </li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(m * n * 3^L)}。
* <ul>
* <li>{@code m} 和 {@code n} 是网格的尺寸，{@code L} 是 {@code word} 的长度。</li>
* <li>外层循环遍历 {@code m * n} 个可能的起始点。</li>
* <li>对于每个起始点，DFS 最坏情况下需要进行 {@code L} 层递归。在每层递归中，除了第一个字符，后续字符有最多 {@code 3} 个方向可以探索（因为不能回到上一个格子）。
* (例如，如果当前是从 {@code 上} 来的，那么不能再回 {@code 下}，所以只有 {@code 上、左、右} 3 个方向)</li>
* <li>因此，DFS 部分的时间复杂度是 {@code O(3^L)}。</li>
* <li>总时间复杂度是 {@code O(m * n * 3^L)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(L)}。
* <ul>
* <li>主要是递归栈的深度，最大为 {@code L} (单词的长度)。</li>
* <li>由于我们修改 {@code board} 来原地标记已访问，所以不需要额外的 {@code visited} 数组空间。</li>
* </ul>
* </li>
* </ul>
*/
public boolean exist(char[][] board, String word) {
if (board == null || board.length == 0 || board[0].length == 0) {
return false;
}
if (word == null || word.isEmpty()) {
return true; // 空单词通常被认为是存在的
}
int m = board.length; // 行数
int n = board[0].length; // 列数
// 遍历网格中的每一个单元格，尝试作为单词的起点
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
// 如果当前单元格的字符与 word 的第一个字符匹配，则开始 DFS 搜索
if (board[i][j] == word.charAt(0)) {
if (dfs(board, word, 0, i, j)) {
return true; // 找到单词，立即返回 true
}
}
}
}
return false; // 遍历所有可能的起点都没有找到单词
}
/**
* 深度优先搜索（DFS）辅助函数。
*
* @param board 字符网格
* @param word 目标单词
* @param index 当前正在匹配 word 的第 index 个字符
* @param r 当前单元格的行索引
* @param c 当前单元格的列索引
* @return 如果从 (r, c) 开始能够找到 word 的剩余部分，则返回 true
*/
private boolean dfs(char[][] board, String word, int index, int r, int c) {
// 递归终止条件 1：成功匹配
// 如果 index 已经达到 word 的长度，说明 word 中的所有字符都已成功匹配
if (index == word.length()) {
return true;
}
// 递归终止条件 2：失败情况 (剪枝)
// 1. 越界检查
if (r < 0 || r >= board.length || c < 0 || c >= board[0].length) {
return false;
}
// 2. 字符不匹配检查
// board[r][c] == '#' 说明该单元格已被当前路径访问过，也属于不匹配
if (board[r][c] != word.charAt(index)) {
return false;
}
// --- DFS 核心步骤 ---
// 1. 标记当前单元格为已访问
char originalChar = board[r][c]; // 保存当前单元格的原始字符
board[r][c] = '#'; // 临时修改为特殊字符，表示已访问
// 2. 向四个方向探索 (递归)
// 尝试向 上、下、左、右 四个相邻方向继续搜索下一个字符
boolean found = dfs(board, word, index + 1, r + 1, c) || // 向下
dfs(board, word, index + 1, r - 1, c) || // 向上
dfs(board, word, index + 1, r, c + 1) || // 向右
dfs(board, word, index + 1, r, c - 1); // 向左
// 3. 撤销标记 (回溯)
// 无论是否找到单词，在当前 DFS 调用结束前，必须将单元格恢复为原始字符
// 允许其他路径在后续的搜索中重新使用这个单元格
board[r][c] = originalChar;
// 返回探索结果
return found;
}分割回文串
java
/**
* <p>此方法解决“分割回文串”问题，采用经典的<strong>回溯算法</strong>。</p>
* <p>核心思想：这是一个典型的组合问题。我们需要将字符串 {@code s} 递归地分解为多个子串。
* 在每一步，我们从当前起始位置，尝试切割出一个子串。如果这个子串是回文串，
* 我们就将其添加到当前组合中，并对字符串的剩余部分进行递归处理。
* 当字符串的所有部分都被成功分解为回文子串时，我们就得到了一个完整的分割方案。</p>
*
* <h3>算法步骤：</h3>
* <ol>
* <li><strong>主函数 {@code partition(s)}：</strong>
* <ul>
* <li>{@code List<List<String>> result = new ArrayList<>();}：用于存储所有找到的分割方案。</li>
* <li>{@code List<String> currentPartition = new ArrayList<>();}：用于存储当前正在构建的分割方案。</li>
* <li>调用辅助的回溯函数 {@code backtrack(s, 0, currentPartition, result)}。初始 {@code startIndex} 为 {@code 0}。</li>
* <li>返回 {@code result}。</li>
* </ul>
* </li>
* <li><strong>回溯辅助函数 {@code backtrack(s, startIndex, currentPartition, result)}：</strong>
* <ul>
* <li><strong>参数：</strong>
* <ul>
* <li>{@code s}: 原始字符串。</li>
* <li>{@code startIndex}: 当前递归层级中，从 {@code s} 的哪个索引开始尝试切割子串。</li>
* <li>{@code currentPartition}: 当前正在构建的分割方案。</li>
* <li>{@code result}: 存储所有完整有效分割方案的列表。</li>
* </ul>
* </li>
* <li><strong>递归终止条件 (Base Case)：</strong>
* <ul>
* <li>{@code if (startIndex == s.length())}：如果 {@code startIndex} 已经到达字符串的末尾（说明 {@code s} 的所有部分都已成功分割）。
* <ul>
* <li>{@code result.add(new ArrayList<>(currentPartition));}：将当前 {@code currentPartition} 的一个<strong>副本</strong>添加到 {@code result} 中。必须是副本。</li>
* <li>{@code return;}：终止当前递归分支。</li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>递归选择与探索：</strong>
* <ul>
* <li>{@code for (int i = startIndex; i < s.length(); i++)}：
* 从 {@code startIndex} 开始，遍历到字符串的末尾。{@code i} 代表当前尝试切割的子串的结束索引。
* 这样，{@code s.substring(startIndex, i + 1)} 就表示当前尝试的子串。</li>
* <li>{@code String sub = s.substring(startIndex, i + 1);}：截取当前子串。</li>
* <li><strong>约束 (回文判断)：</strong>
* <ul>
* <li>{@code if (isPalindrome(sub))}：只有当 {@code sub} 是一个回文串时，才继续探索。
* <ul>
* <li><strong>选择 (Choose)：</strong>
* <ul>
* <li>{@code currentPartition.add(sub);}：将 {@code sub} 加入当前分割方案。</li>
* </ul>
* </li>
* <li><strong>探索 (Explore)：</strong>
* <ul>
* <li>{@code backtrack(s, i + 1, currentPartition, result);}：递归调用，从 {@code i + 1} 位置开始处理字符串的剩余部分。</li>
* </ul>
* </li>
* <li><strong>撤销 (Unchoose/Backtrack)：</strong>
* <ul>
* <li>{@code currentPartition.removeLast();}：回溯，移除最后添加的子串，以便尝试当前 {@code startIndex} 的其他切割点。</li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* </ul>
* </li>
* <li><strong>辅助函数 {@code isPalindrome(String str)}：</strong>
* <ul>
* <li>使用双指针 {@code left} 和 {@code right} 从字符串两端向中间移动进行比较。</li>
* <li>{@code while (left < right)}：如果 {@code str.charAt(left) != str.charAt(right)}，则不是回文串，返回 {@code false}。</li>
* <li>如果循环结束，说明是回文串，返回 {@code true}。</li>
* </ul>
* </li>
* </ol>
*
* <h3>性能分析：</h3>
* <ul>
* <li><strong>时间复杂度：</strong> {@code O(N * 2^N)}。
* <ul>
* <li>{@code N} 是字符串 {@code s} 的长度。</li>
* <li>在最坏情况下，字符串的所有单个字符都是回文，例如 {@code s = "aaaaa"}。
* 每个位置都可以切或不切，导致 {@code 2^(N-1)} 种切割方式。
* 对于每种切割，回文判断和字符串创建等操作会带来额外开销。</li>
* <li>{@code isPalindrome} 函数每次调用需要 {@code O(N)} 的时间。而回溯的深度也可能是 {@code N}。</li>
* <li>粗略估计，回溯树的每个节点，我们可能要尝试 {@code N} 次切割，每次切割都要检查 {@code O(N)} 的回文。
* 总的来说，这是一个指数级的问题，通常认为在 {@code O(N * 2^N)} 或者 {@code O(N^2 * 2^N)} 之间。</li>
* <li>更精确的分析是，对于长度为 N 的字符串，可能的切割方式是 {@code 2^(N-1)} 种。
* 对于每种切割，都会产生 {@code O(N)} 个子串，每个子串的最大长度是 {@code N}，判断其回文性最坏 {@code O(N)}。
* 所以总时间是 {@code O(2^N * N^2)}。若不考虑 {@code isPalindrome} 的字符串创建开销，则为 {@code O(2^N * N)}。</li>
* </ul>
* </li>
* <li><strong>空间复杂度：</strong> {@code O(N)}。
* <ul>
* <li>递归栈的深度最大为 {@code N}。</li>
* <li>{@code currentPartition} 列表的长度也最大为 {@code N}。</li>
* <li>如果将结果列表计算在内，则空间复杂度为 {@code O(2^N * N)}。这里的 {@code O(N)} 指的是递归栈和辅助 {@code currentPartition} 列表的空间。</li>
* </ul>
* </li>
* </ul>
*/
public List<List<String>> partition(String s) {
List<List<String>> result = new ArrayList<>(); // 存储所有分割方案
List<String> currentPartition = new ArrayList<>(); // 存储当前正在构建的分割方案
// 调用回溯辅助函数
backtrack(s, 0, currentPartition, result);
return result;
}
/**
* 回溯辅助函数，用于生成所有回文分割方案。
*
* @param s 原始字符串
* @param startIndex 当前切割的起始索引
* @param currentPartition 当前正在构建的分割方案
* @param result 存储所有完整有效分割方案的列表
*/
private void backtrack(String s, int startIndex,
List<String> currentPartition, List<List<String>> result) {
// 递归终止条件：如果 startIndex 已经到达字符串的末尾
// 说明 s 的所有部分都已成功分割为回文串
if (startIndex == s.length()) {
// 将当前组合的副本添加到结果列表中
result.add(new ArrayList<>(currentPartition));
return; // 终止当前递归分支
}
// 递归选择与探索：从 startIndex 开始，尝试不同的切割点
// i 代表当前子串的结束索引
for (int i = startIndex; i < s.length(); i++) {
// 截取当前尝试的子串 s[startIndex...i]
String sub = s.substring(startIndex, i + 1);
// 约束：只有当子串是回文串时，才继续探索
if (isPalindrome(sub)) {
// 1. 选择：将回文子串加入当前分割方案
currentPartition.add(sub);
// 2. 探索：递归调用，处理字符串的剩余部分，起始索引变为 i + 1
backtrack(s, i + 1, currentPartition, result);
// 3. 撤销：回溯，移除最后添加的子串，尝试当前 startIndex 的其他切割点
currentPartition.removeLast();
}
}
}
/**
* 辅助函数：判断一个字符串是否是回文串。
*
* @param str 待判断的字符串
* @return 如果是回文串则返回 true，否则返回 false
*/
private boolean isPalindrome(String str) {
int left = 0;
int right = str.length() - 1;
while (left < right) {
if (str.charAt(left) != str.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}N 皇后
java
/**
* TODO
*/贡献者
LI SIR