Day23--回溯--39. 组合总和，40. 组合总和 II，131. 分割回文串

Day23–回溯–39. 组合总和，40. 组合总和 II，131. 分割回文串

39. 组合总和

思路：

递归法（回溯）。因为可以重复取，所以下一层的startIndex还是i，sum要加上本层元素的值

// 递归法（回溯）。因为可以重复取，所以下一层的startIndex还是i，sum要加上本层元素的值
class Solution {

    // 结果集
    List<List<Integer>> res = new ArrayList<>();
    // 路径上的元素
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backtracking(candidates, target, 0, 0);
        return res;
    }

    // 要有startIndex才能知道下一层从哪里开始，要有sum，才知道路径上的和有多少
    private void backtracking(int[] nums, int target, int startIndex, int sum) {
        // sum超出了，返回
        if (sum > target) {
            return;
        }
        // sum 刚好，加入结果集
        if (sum == target) {
            res.add(new ArrayList(path));
        }

        for (int i = startIndex; i < nums.length; i++) {
            // 加入本层节点
            path.add(nums[i]);
            // 注意，因为可以重复取，所以下一层的startIndex还是i，sum要加上本层元素的值
            backtracking(nums, target, i, sum + nums[i]);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}

40. 组合总和 II

与39. 组合总和不同的是，要去重。其一是不能重复取值，其二是不能有重复的集合。前者可以想象成：startIndex+1传到下一层；后者的意思是，同一层的相同元素不能重复取。

思路：

• 递归法（回溯）。因为不可以重复取，所以下一层的startIndex是 i+1 ，sum要加上本层元素的值
• 注意：解集不能包含重复的组合。 ——重点在于去重
• 去重：每一层不能重复取相同的元素——解决办法：先排序，然后nums[i]!=nums[i-1]

// 递归法（回溯）。因为不可以重复取，所以下一层的startIndex是 i+1 ，sum要加上本层元素的值
// 注意：解集不能包含重复的组合。 ——重点在于去重
// 去重：每一层不能重复取相同的元素——解决办法：先排序，然后nums[i]!=nums[i-1]
class Solution {

    // 结果集
    List<List<Integer>> res = new ArrayList<>();
    // 路径上的元素
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, 0);
        return res;
    }

    // 要有startIndex才能知道下一层从哪里开始，要有sum，才知道路径上的和有多少
    private void backtracking(int[] nums, int target, int startIndex, int sum) {
        // sum超出了，返回
        if (sum > target) {
            return;
        }
        // sum 刚好，加入结果集
        if (sum == target) {
            res.add(new ArrayList(path));
        }

        for (int i = startIndex; i < nums.length; i++) {
            // 对于同一层的元素，去重。
            if (i > startIndex && nums[i] == nums[i - 1]) {
                continue;
            }
            // 加入本层节点
            path.add(nums[i]);
            // 注意，因为不可以重复取，所以下一层的startIndex是 i+1 ，sum要加上本层元素的值
            backtracking(nums, target, i + 1, sum + nums[i]);
            // 回溯
            path.remove(path.size() - 1);
        }
    }
}

131. 分割回文串

思路：

太晕了。绕晕了。回头二刷再做。

public class Solution {
    private List<List<String>> result = new ArrayList<>();
    private List<String> path = new ArrayList<>(); // 存储当前已经找到的回文子串

    // 主方法，返回所有可能的回文分割方案
    public List<List<String>> partition(String s) {
        backtracking(s, 0);
        return result;
    }

    // 回溯算法
    private void backtracking(String s, int startIndex) {
        // 如果起始位置已经超出字符串长度，说明找到一组组分割方案
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }

        for (int i = startIndex; i < s.length(); i++) {
            // 检查从startIndex到i的子串是否是回文
            if (isPalindrome(s, startIndex, i)) {
                // 获取子串并加入路径
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                // 不是回文，跳过
                continue;
            }

            // 递归处理下一个位置
            backtracking(s, i + 1);
            // 回溯，移除最后添加的子串
            path.remove(path.size() - 1);
        }
    }

    // 检查子串是否是回文
    private boolean isPalindrome(String s, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}