Leetcode+JAVA+回溯

39.组合总和

给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

输入: candidates = [2], target = 1
输出: []

提示：

• 1 <= candidates.length <= 30
• 2 <= candidates[i] <= 40
• candidates 的所有元素 互不相同
• 1 <= target <= 40

解题思路

这个问题要求从给定的无重复整数数组 candidates 中找出所有和为目标值 target 的不同组合，允许每个数字无限制重复使用。我们使用 回溯法 来解决这个问题，核心思路如下：

1. 回溯法：
   • 遍历 candidates 中的每个数字，尝试将其加入当前组合。
   • 递归调用继续选择数字（可以选择当前数字或后续数字），更新当前和 sum。
   • 如果当前和等于 target，将组合加入结果集；如果超过 target，终止当前分支。
   • 使用回溯撤销当前选择，尝试其他可能性。
2. 避免重复组合：
   • 通过参数 index 限制每次选择从当前索引开始，确保组合按顺序生成（如 [2,3] 不会重复为 [3,2]）。
   • 允许重复使用同一个数字，因此递归时传递相同的 index（backtrack(..., i)）。
3. 剪枝优化：
   • 如果当前和加上当前数字超过 target（sum + candidates[i] > target），终止当前分支。
   • 预先对 candidates 排序，确保数字按升序处理，进一步优化剪枝（当和超过 target 时，后续更大数字无需尝试）。
4. 终止条件：
   • 当当前和 sum == target 时，将当前组合加入结果集 ans。
5. 特殊情况：
   • 如果 target 小于 candidates 中最小值，或数组为空，则无解，返回空列表。

时间和空间复杂度

• 时间复杂度：O(N * 2^N)，其中 N 是 candidates 的长度。在最坏情况下，每个数字可以选或不选，生成所有可能的组合。实际复杂度因剪枝而低于理论值。
• 空间复杂度：O(target / min(candidates))，用于递归栈的最大深度（最坏情况下，组合由最小数字组成）。结果集空间不计入复杂度。

代码 

import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 初始化结果集，存储所有有效组合
        List<List<Integer>> ans = new ArrayList<>();
        // 初始化临时列表，存储当前组合
        List<Integer> temp = new ArrayList<>();
        // 排序数组，便于剪枝
        Arrays.sort(candidates);
        // 开始回溯，从索引 0 开始
        backtrack(candidates, target, 0, temp, ans, 0);
        return ans;
    }

    /**
     * 回溯方法，生成所有和为 target 的组合
     * @param candidates 候选数字数组
     * @param target 目标和
     * @param sum 当前组合的和
     * @param temp 当前正在构建的组合
     * @param ans 结果集，存储所有有效组合
     * @param index 当前选择的起始索引
     */
    private void backtrack(int[] candidates, int target, int sum, List<Integer> temp, List<List<Integer>> ans, int index) {
        // 终止条件：当前和等于 target，加入结果集
        if (sum == target) {
            ans.add(new ArrayList<>(temp));
            return;
        }
        // 从 index 开始遍历候选数字
        for (int i = index; i < candidates.length; i++) {
            // 剪枝：如果当前和加上当前数字超过 target，终止（因数组已排序，后续数字更大）
            if (sum + candidates[i] > target) {
                break;
            }
            // 选择当前数字
            temp.add(candidates[i]);
            // 递归调用，允许重复选择当前数字（传递 i）
            backtrack(candidates, target, sum + candidates[i], temp, ans, i);
            // 回溯：移除最后一个数字，恢复状态
            temp.remove(temp.size() - 1);
        }
    }
}

40.组合总和II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。 

示例 1:

输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]

提示:

• 1 <= candidates.length <= 100
• 1 <= candidates[i] <= 50
• 1 <= target <= 30

解题思路

这个问题要求从给定的候选数字数组 candidates 中找出所有和为目标值 target 的组合，每个数字只能使用一次，且结果不能包含重复组合。由于可能存在重复数字，我们需要特别处理去重逻辑。使用 回溯法 解决，核心思路如下：

1. 回溯法：
   • 遍历 candidates，将每个数字尝试加入当前组合。
   • 递归选择后续数字，更新当前和 sum，直到和达到 target 或超过。
   • 使用回溯撤销选择，尝试其他可能性。
2. 去重逻辑：
   • 为了避免重复组合（如 [1,2,5] 和 [1,2,5]），对 candidates 预先排序，将相同数字放在一起。
   • 在同一树层中，跳过重复的数字（通过 i > start && candidates[i] == candidates[i-1] 判断）。
   • 使用 start 参数确保每个数字只在当前组合中选择一次（递归时传递 i+1）。
3. 剪枝优化：
   • 如果当前和加上当前数字超过 target（sum + candidates[i] > target），终止当前分支。
   • 排序后，当和超过 target 时，后续更大数字无需尝试。
4. 终止条件：
   • 当当前和 sum == target 时，将当前组合加入结果集 res。
5. 数据结构：
   • 使用 LinkedList 存储当前组合 path，便于尾部操作。
   • 使用全局变量 sum 跟踪当前和，减少参数传递。

时间和空间复杂度

• 时间复杂度：O(2^N)，其中 N 是 candidates 的长度。最坏情况下，每个数字选或不选，生成所有可能组合。去重和剪枝降低实际复杂度。
• 空间复杂度：O(N)，用于递归栈和当前组合 path。结果集空间不计入复杂度。

代码 

import java.util.*;

class Solution {
    // 结果集，存储所有有效组合
    private List<List<Integer>> res = new ArrayList<>();
    // 当前组合，使用 LinkedList 便于尾部操作
    private LinkedList<Integer> path = new LinkedList<>();
    // 当前组合的和
    private int sum = 0;

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        // 排序数组，便于去重和剪枝
        Arrays.sort(candidates);
        // 开始回溯，从索引 0 开始
        backTracking(candidates, target, 0);
        return res;
    }

    /**
     * 回溯方法，生成所有和为 target 的组合
     * @param candidates 候选数字数组（已排序）
     * @param target 目标和
     * @param start 当前选择的起始索引，避免重复使用同一数字
     */
    private void backTracking(int[] candidates, int target, int start) {
        // 终止条件：当前和等于 target，加入结果集
        if (sum == target) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 遍历从 start 开始的候选数字
        for (int i = start; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 去重：跳过同一树层的重复数字
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue;
            }
            // 选择当前数字
            sum += candidates[i];
            path.add(candidates[i]);
            // 递归调用，选择下一个数字（i+1 确保每个数字只用一次）
            backTracking(candidates, target, i + 1);
            // 回溯：移除最后一个数字，恢复状态
            sum -= path.remove(path.size() - 1);
        }
    }
}

131.分割回文串

给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

输入：s = "a"
输出：[["a"]]

提示：

• 1 <= s.length <= 16
• s 仅由小写英文字母组成

解题思路

这个问题要求将字符串 s 分割成若干子串，使得每个子串都是回文串，并返回所有可能的分割方案。由于需要探索所有可能的分割方式，我们使用 回溯法 来解决，核心思路如下：

1. 回溯法：
   • 从字符串的起始位置 start 开始，尝试所有可能的子串（从 start 到 i）。
   • 如果当前子串是回文串，将其加入当前分割方案 cur，然后递归处理剩余部分（从 i+1 开始）。
   • 使用回溯撤销当前子串，尝试其他可能的子串。
2. 回文检查：
   • 编写一个辅助方法 check，用于判断子串是否为回文。
   • 回文检查通过比较字符串两端的字符是否相等实现。
3. 终止条件：
   • 当起始索引 start 达到字符串长度 s.length()，说明当前分割方案完整，将其加入结果集 res。
4. 去重与优化：
   • 由于输入字符串仅由小写英文字母组成，且分割是连续的，无需特别处理重复组合。
   • 使用 StringBuilder 构建子串，但可以优化为直接截取子串，减少额外空间。
5. 特殊情况：
   • 如果输入字符串为空（题目保证长度至少为 1），无需处理。

时间和空间复杂度

• 时间复杂度：O(N * 2^N)，其中 N 是字符串 s 的长度。分割方案的数量为 O(2^N)（每个字符可以选择是否分割），每次检查回文和复制组合需要 O(N)。
• 空间复杂度：O(N)，用于递归栈（最大深度为 N）和当前分割方案 cur。结果集空间不计入复杂度。

代码

import java.util.*;

class Solution {
    // 结果集，存储所有有效分割方案
    private List<List<String>> res = new ArrayList<>();
    // 当前分割方案
    private List<String> cur = new ArrayList<>();

    public List<List<String>> partition(String s) {
        // 从索引 0 开始回溯
        backtracking(s, 0);
        return res;
    }

    /**
     * 回溯方法，生成所有可能的回文分割方案
     * @param s 输入字符串
     * @param start 当前分割的起始索引
     */
    private void backtracking(String s, int start) {
        // 终止条件：如果起始索引达到字符串长度，当前方案有效
        if (start == s.length()) {
            res.add(new ArrayList<>(cur));
            return;
        }
        // 尝试从 start 到 i 的子串
        for (int i = start; i < s.length(); i++) {
            // 检查子串 s[start:i+1] 是否为回文
            if (isPalindrome(s, start, i)) {
                // 添加当前回文子串到方案
                cur.add(s.substring(start, i + 1));
                // 递归处理剩余部分
                backtracking(s, i + 1);
                // 回溯：移除最后一个子串
                cur.remove(cur.size() - 1);
            }
        }
    }

    /**
     * 辅助方法，检查子串 s[left:right+1] 是否为回文
     * @param s 输入字符串
     * @param left 子串起始索引
     * @param right 子串结束索引
     * @return 是否为回文
     */
    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

10.复原IP地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

• 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

• 1 <= s.length <= 20
• s 仅由数字组成

解题思路

这个问题要求将给定的数字字符串 s 分割成四个部分，形成有效的 IP 地址（每个部分为 0 到 255 的整数，且无前导零）。我们使用 回溯法 来尝试所有可能的分割方案，核心思路如下：

1. 回溯法：
   • 将字符串 s 分割成四段，每段长度为 1 到 3 位。
   • 使用递归尝试从起始索引 start 开始的每种可能段长度，检查是否有效。
   • 如果当前段有效，加入当前组合，继续递归处理剩余部分。
   • 使用回溯撤销当前段，尝试其他长度。
2. 有效性检查：
   • 每段必须是 0 到 255 的整数。
   • 禁止前导零（例如 "01" 或 "001" 无效）。
   • 每段长度为 1 到 3 位。
   • 使用辅助方法 isValid 检查段是否符合规则。
3. 剪枝优化：
   • 输入字符串长度必须在 4 到 12 之间（少于 4 位无法形成四段，超过 12 位无法都满足 1-3 位限制）。
   • 剩余字符数量必须满足剩余段数的需求：remaining >= 4 - num（每段至少 1 位）且 remaining <= 3 * (4 - num)（每段最多 3 位）。
   • 如果段数超过 4 或起始索引超出字符串长度，终止。
4. 终止条件：
   • 当分割出 4 段且用完所有字符（num == 4 && start == s.length()），将当前组合加入结果集。
   • 去掉结果中末尾的点（.）以符合 IP 地址格式。
5. 数据结构：
   • 使用 StringBuilder 高效构建当前 IP 地址，减少字符串拼接开销。
   • 使用 List<String> 存储所有有效 IP 地址。

时间和空间复杂度

• 时间复杂度：O(3^4 * N) = O(N)，其中 N 是字符串长度。每个段有最多 3 种长度选择（1、2、3），共 4 段，生成组合数量固定（3^4 = 81），每次处理涉及字符串操作 O(N)。
• 空间复杂度：O(N)，用于递归栈（最大深度 4）和 StringBuilder 存储当前组合。结果集空间不计入复杂度。

代码 

import java.util.*;

class Solution {
    // 结果集，存储所有有效 IP 地址
    private List<String> ans = new ArrayList<>();

    public List<String> restoreIpAddresses(String s) {
        // 边界检查：字符串长度必须在 4 到 12 之间
        if (s == null || s.length() < 4 || s.length() > 12) {
            return ans;
        }
        // 开始回溯，从索引 0 开始，初始段数为 0
        backtracking(s, new StringBuilder(), 0, 0);
        return ans;
    }

    /**
     * 回溯方法，生成所有可能的有效 IP 地址
     * @param s 输入数字字符串
     * @param sb 当前构建的 IP 地址
     * @param start 当前处理的字符串起始索引
     * @param segmentCount 当前已分割的段数
     */
    private void backtracking(String s, StringBuilder sb, int start, int segmentCount) {
        // 终止条件：分割出 4 段且用完所有字符
        if (segmentCount == 4 && start == s.length()) {
            ans.add(sb.toString().substring(0, sb.length() - 1)); // 去掉末尾的点
            return;
        }
        // 剪枝：段数超限或字符不足/过多
        if (segmentCount > 4 || start >= s.length()) {
            return;
        }
        int remaining = s.length() - start;
        if (remaining < (4 - segmentCount) || remaining > 3 * (4 - segmentCount)) {
            return;
        }
        // 尝试长度为 1 到 3 的段
        for (int len = 1; len <= 3 && start + len <= s.length(); len++) {
            String segment = s.substring(start, start + len);
            // 检查当前段是否有效
            if (isValid(segment)) {
                int sbLen = sb.length();
                // 添加当前段和点
                sb.append(segment).append('.');
                // 递归处理下一段
                backtracking(s, sb, start + len, segmentCount + 1);
                // 回溯：恢复 StringBuilder 到之前状态
                sb.setLength(sbLen);
            }
        }
    }

    /**
     * 辅助方法，检查段是否为有效 IP 段
     * @param segment 待检查的段
     * @return 是否有效
     */
    private boolean isValid(String segment) {
        int len = segment.length();
        // 长度必须为 1 到 3
        if (len < 1 || len > 3) {
            return false;
        }
        // 禁止前导零（除了单个 0）
        if (len > 1 && segment.charAt(0) == '0') {
            return false;
        }
        // 转换为整数，检查是否在 0 到 255 之间
        try {
            int value = Integer.parseInt(segment);
            return value >= 0 && value <= 255;
        } catch (NumberFormatException e) {
            return false;
        }
    }
}

78.子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

示例 2：

输入：nums = [0]
输出：[[],[0]]

提示：

• 1 <= nums.length <= 10
• -10 <= nums[i] <= 10
• nums 中的所有元素 互不相同

 

解题思路

这个问题要求返回整数数组 nums 的所有可能子集（幂集），且数组元素互不相同，解集不能包含重复子集。我们可以使用 回溯法 来生成所有子集，核心思路如下：

1. 回溯法：
   • 子集是数组中元素的任意组合（包括空集），可以通过递归选择或不选择每个元素来生成。
   • 使用 start 参数控制当前选择的起始索引，确保子集按顺序生成（避免重复）。
   • 每次递归可以选择当前元素并继续递归，或跳过当前元素递归后续部分。
2. 生成所有子集：
   • 为了生成所有子集，我们可以：
     • 枚举子集长度（从 0 到 nums.length），为每种长度调用回溯。
     • 或者在回溯中允许任意长度，将每次递归的当前组合加入结果集（更简洁）。
   • 由于 nums 元素互不相同，无需额外去重。
3. 优化：
   • 直接在回溯中收集所有子集，无需显式枚举长度。
   • 使用 start 确保每个元素只在后续子集中考虑，避免重复。
4. 终止条件：
   • 回溯中无需显式终止条件，每次递归的当前组合（cur）都可加入结果集。
   • 当索引超出数组长度时，停止递归。
5. 特殊情况：
   • 题目保证数组非空（1 <= nums.length），无需处理空输入。

时间和空间复杂度

• 时间复杂度：O(N * 2^N)，其中 N 是 nums 的长度。数组有 2^N 个子集，每个子集复制到结果集需要 O(N)。
• 空间复杂度：O(N)，用于递归栈（最大深度 N）和当前组合 cur。结果集空间不计入复杂度。

代码

import java.util.*;

class Solution {
    // 结果集，存储所有子集
    private List<List<Integer>> ans = new ArrayList<>();
    // 当前子集
    private List<Integer> cur = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        // 开始回溯，从索引 0 开始
        backtracking(nums, 0);
        return ans;
    }

    /**
     * 回溯方法，生成所有可能的子集
     * @param nums 输入数组
     * @param start 当前选择的起始索引
     */
    private void backtracking(int[] nums, int start) {
        // 每次递归都将当前子集加入结果集（包括空集）
        ans.add(new ArrayList<>(cur));
        // 从 start 开始遍历剩余元素
        for (int i = start; i < nums.length; i++) {
            // 选择当前元素
            cur.add(nums[i]);
            // 递归处理后续元素
            backtracking(nums, i + 1);
            // 回溯：移除最后一个元素
            cur.remove(cur.size() - 1);
        }
    }
}