39. 组合总和

题目链接：39. 组合总和
文档讲解：代码随想录
状态：卡了一会儿

思路：先排序，方便剪枝。允许数字重复使用，因此递归调用时传入当前索引i。

题解：

public class Solution {
    // 用于存储所有可能的组合
    private List<List<Integer>> res = new ArrayList<>();
    // 当前正在构建的组合
    private LinkedList<Integer> list = new LinkedList<>();
    // 用于存储当前组合的和
    private int sum = 0;

    /**
     * 组合求和函数
     * @param candidates 候选数字数组
     * @param target 目标数字
     * @return 所有可能的组合列表
     */
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        // 首先对候选数字进行排序
        Arrays.sort(candidates);
        // 调用回溯函数
        backtracking(candidates, target, 0);
        // 返回所有可能的组合
        return res;
    }

    /**
     * 回溯函数，用于递归地搜索所有可能的组合
     * @param candidates 候选数字数组
     * @param target 目标数字
     * @param startIndex 当前搜索的起始索引
     */
    public void backtracking(int[] candidates, int target, int startIndex) {
        // 如果当前和大于目标，则回溯
        if (sum > target) {
            return;
        }
        // 如果当前和等于目标，将当前组合添加到结果列表中
        if (sum == target) {
            res.add(new ArrayList<>(list));
            return;
        }
        // 遍历候选数字，从startIndex开始，直到sum+当前数字大于目标或遍历完所有数字
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            // 将当前数字添加到当前组合中，并更新当前和
            sum += candidates[i];
            list.add(candidates[i]);
            // 递归调用回溯函数，搜索当前数字之后的组合
            backtracking(candidates, target, i); // 注意这里传入i，允许重复使用同一个数字
            // 回溯，移除当前数字，恢复当前和
            sum -= candidates[i];
            list.removeLast();
        }
    }
}

40.组合总和II

题目链接：40.组合总和II
文档讲解：代码随想录
状态：自己在去重的时候，将集合中的重复元素也去掉了，导致结果缺少。集合（数组candidates）有重复元素，但还不能有重复的组合，这个不会处理。

思路：使用used数组标记树层或树枝中的元素是否使用，从而将集合有重复元素和结果又重复组合区分开。
默认used数组都为false，树层有重复元素和树枝有重复元素的关键区别在于used[i-1]是否为true，树层中元素因为回溯会使used[i-1]恢复成false，树枝中有重复元素则used[i-1]使用过，因此为true。

题解：

    List<List<Integer>> res = new ArrayList<>();  // 结果集
    LinkedList<Integer> list = new LinkedList<>();  // 当前组合
    int sum = 0;  // 当前组合的和

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);  // 排序，方便后续处理
        boolean[] used = new boolean[candidates.length];  // 记录每个元素是否被使用过
        Arrays.fill(used, false);  // 初始化为未使用
        backtracking(candidates, used, target, 0);  // 开始回溯
        return res;  // 返回结果集
    }

    public void backtracking(int[] candidates, boolean[] used, int target, int startIndex) {
        if (sum == target) {  // 当前组合的和等于目标值
            res.add(new ArrayList<>(list));  // 将当前组合加入结果集
            return;
        }
        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) {  // 去重
                continue;
            }
            sum += candidates[i];  // 做出选择，更新当前组合的和
            list.add(candidates[i]);  // 将当前元素加入当前组合
            used[i] = true;  // 标记当前元素已被使用
            backtracking(candidates, used, target, i + 1);  // 递归，处理下一个元素
            list.removeLast();  // 撤销选择，回溯到上一个状态
            used[i] = false;  // 标记当前元素未被使用
            sum -= candidates[i];  // 更新当前组合的和
        }
    }

131.分割回文串

题目链接：131.分割回文串
文档讲解：代码随想录
状态：不会，想到分割方法，代码没写出来！

代码没写出来的原因：

1. 写成了 if (startIndex == chars.length) { res.add(new ArrayList<>(list)); return; }认为 startIndex == chars.length - 1 时将list添加到res中。实际上因为backtracking(chars, i + 1);的存在，res中添加list的操作都是在下次递归中完成的，而这时i+1就导致startIndex每次都比原来的大了1。
2. 写成了new String(chars, startIndex, i)，而实际上第三个参数是长度

    // 存储所有分割方案的列表
    List<List<String>> res = new ArrayList<>();
    // 当前正在构建的分割方案
    LinkedList<String> list = new LinkedList<>();

    /**
     * 将字符串分割成回文子串的方案
     * @param s 输入的字符串
     * @return 分割方案的列表
     */
    public List<List<String>> partition(String s) {
        // 将字符串转换为字符数组
        char[] chars = s.toCharArray();
        // 从索引0开始回溯
        backtracking(chars, 0);
        // 返回所有分割方案
        return res;
    }

    /**
     * 回溯函数，用于递归地搜索所有可能的回文子串分割方案
     * @param chars 字符串转换后的字符数组
     * @param startIndex 当前搜索的起始索引
     */
    public void backtracking(char[] chars, int startIndex) {
        // 如果当前索引等于字符数组的长度，说明已经处理完所有字符，将当前方案添加到结果中
        if (startIndex == chars.length) {
            res.add(new ArrayList<>(list));
            return;
        }
        // 从当前索引开始，尝试所有可能的分割点
        for (int i = startIndex; i < chars.length; i++) {
            // 如果从startIndex到i的子串是回文串，则将其添加到当前方案中
            if (isPalindrome(chars, startIndex, i)) {
                // 添加子串到当前方案
                list.add(new String(chars, startIndex, i - startIndex + 1));
                // 递归调用回溯函数，继续搜索i之后的分割方案
                backtracking(chars, i + 1);
                // 回溯，移除最后一个添加的子串，以便尝试其他分割方案
                list.removeLast();
            }
        }
    }

    /**
     * 判断子串是否为回文串
     * @param chars 字符数组
     * @param start 子串的起始索引
     * @param end 子串的结束索引
     * @return 如果子串是回文串返回true，否则返回false
     */
    public boolean isPalindrome(char[] chars, int start, int end) {
        // 从子串的两端向中间遍历，如果字符不相等则不是回文串
        while (start <= end) {
            if (chars[start] != chars[end]) {
                return false;
            }
            start++;
            end--;
        }
        // 如果遍历完所有字符都相等，则子串是回文串
        return true;
    }