代码随想录算法训练营，9月19日 | 39. 组合总和，40.组合总和II，131.分割回文串

39. 组合总和
题目链接：39. 组合总和
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰组合总和
日期：2024-09-19

想法：组合总和类型题，允许重复使用元素，递归不+1就行。
Java代码如下：

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public void backTracking(int[] candidates, int target, int startIndex){
        if(target < 0){
            return;
        }
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++){
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i);
            path.removeLast();
            target += candidates[i];
        }
    }
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates, target, 0);
        return res;
    }
}

40.组合总和II
题目链接：40.组合总和II
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰组合总和II
日期：2024-09-19

想法：去重挺麻烦，第一遍没思路。
Java代码如下：

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    boolean[] used;
    public void backTracking(int[] candidates, int target, int startIndex){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++){
            if(i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false){
                continue;
            }
            path.add(candidates[i]);
            used[i] = true;
            target -= candidates[i];
            backTracking(candidates, target, i + 1);
            path.removeLast();
            target += candidates[i];
            used[i] = false;
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        used = new boolean[candidates.length];
        Arrays.fill(used, false);
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return res;
    }
}

总结：使用boolean used数组来表示数组中元素用没用，先将数组排序，使同样的数字在一起，uesd数组巧妙就巧妙在，如果used[i-1]为true，说明现在的i是在树枝上，used[i-1]为false，说明i现在是在同一树层上，这时判断candidates[i] == candidates[i - 1]就能直到是不是在同一层用过前一个相同大小的数了，做到了去重。在理解了用used数组的基础上就可以考虑不用它:

class Solution {
    List<Integer> path = new ArrayList<>();
    List<List<Integer>> res = new ArrayList<>();
    public void backTracking(int[] candidates, int target, int startIndex){
        if(target < 0) return;
        if(target == 0){
            res.add(new ArrayList(path));
            return;
        }
        for(int i = startIndex; i < candidates.length; i++){
            if(i > startIndex && candidates[i] == candidates[i - 1]){
                continue;
            }
            path.add(candidates[i]);
            target -= candidates[i];
            backTracking(candidates, target, i + 1);
            path.removeLast();
            target += candidates[i];
        }
    }
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        backTracking(candidates, target, 0);
        return res;
    }
}

在（横向）同一层的时候需要判断前一个数是否和现在的相等，而递归（纵向）时就正常i+1往下走就行。

131.分割回文串
题目链接：131.分割回文串
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰分割回文串
日期：2024-09-19

想法：构成树的思路，横向，切一刀，从不同位置从左到右，纵向每一层在之前切一刀的位置的后面加1刀。
Java代码如下：

class Solution {
    List<List<String>> res = new ArrayList<>();
    List<String> path = new ArrayList<>();

    private void backtracking(String s, int startIndex, StringBuilder sb){
        if (startIndex >= s.length()){
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++){
            sb.append(s.charAt(i));
            if (check(sb)){
                path.add(sb.toString());
                backtracking(s, i + 1, new StringBuilder());
                path.removeLast();
            }
        }
    }

    private boolean check(StringBuilder sb){
        for(int i = 0, j = sb.length() - 1; i < j; i++, j--){
            if(sb.charAt(i) != sb.charAt(j)) return false;
        }
        return true;
    }

    public List<List<String>> partition(String s){
        backtracking(s, 0, new StringBuilder());
        return res;
    }

}

总结：判断回文双指针。