代码随想录算法训练营第二十三天-39组合总和、40组合总和II、131分割回文串

前言
状态：39AC 但是可以继续优化剪枝。40AC。131 分割没有做过，直接看解析了（动态规划求回文这个没有看，后面刷到动态规划再研究）。
更新

1	24-06-11 初始记录

初步题解

39 组合总和

题目链接：(https://leetcode.cn/problems/combination-sum)

public static List<List<Integer>> combinationSum(int[] candidates, int target) {  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    combinationSumDFS(0, 0, target, candidates, resultOne, result);  
    return result;  
}  
  
  
private static void combinationSumDFS(int startIndex, int sum, int target, int[] candidates, List<Integer> resultOne, List<List<Integer>> result) {  
    if (sum >= target) {  
        if (target == sum) {  
            result.add(new ArrayList<>(resultOne));  
        }  
        return;  
    }  
  
    for (int i = startIndex; i < candidates.length; i++) {  
        resultOne.add(candidates[i]);  
        combinationSumDFS(i, sum + candidates[i], target, candidates, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

40 组合总和 II

题目链接：(https://leetcode.cn/problems/combination-sum-ii)

public static List<List<Integer>> combinationSum2(int[] candidates, int target) {  
    Arrays.sort(candidates);  
  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    combinationSum2DFS(0, 0, target, candidates, resultOne, result);  
    return result;  
}  
  
/**  
 * 思路：  
 * 1. 和上题差不多。但是数组变成有重复元素的了。  
 * 2. 想法是每层遍历的时候，去重  
 */  
private static void combinationSum2DFS(int startIndex, int sum, int target, int[] candidates, List<Integer> resultOne, List<List<Integer>> result) {  
    if (sum == target) {  
        result.add(new ArrayList<>(resultOne));  
        return;  
    }  
  
    for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
		// 在单层的数组内去重
        if (i - 1 >= startIndex && candidates[i] == candidates[i - 1]) {  
            continue;  
        }  
        resultOne.add(candidates[i]);  
        combinationSum2DFS(i + 1, sum + candidates[i], target, candidates, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

131 分割回文串

题目链接：(https://leetcode.cn/problems/palindrome-partitioning)

看解析

39 组合总和

题目链接/文章讲解：(https://programmercarl.com/0039.组合总和.html)

视频讲解：(https://www.bilibili.com/video/BV1KT4y1M7HJ/)

本来以为只要 return 就不用优化了（好像没有什么关系，还是会继续往下走），但是题解中说可以减少一次进入递归。

public static List<List<Integer>> combinationSum(int[] candidates, int target) {  
    // 要剪枝必须要排序  
    Arrays.sort(candidates);  
  
    List<List<Integer>> result = new ArrayList<>();  
    List<Integer> resultOne = new ArrayList<>();  
  
    combinationSumDFS(0, 0, target, candidates, resultOne, result);  
    return result;  
}  
  
  
private static void combinationSumDFS(int startIndex, int sum, int target, int[] candidates, List<Integer> resultOne, List<List<Integer>> result) {  
    if (target == sum) {  
        result.add(new ArrayList<>(resultOne));  
        return;  
    }  
  
    // for循环的判断做了剪枝优化处理  
    for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {  
        resultOne.add(candidates[i]);  
        combinationSumDFS(i, sum + candidates[i], target, candidates, resultOne, result);  
        resultOne.remove(resultOne.size() - 1);  
    }  
}

40 组合总和 II

题目链接/文章讲解：(https://programmercarl.com/0040.组合总和II.html)

视频讲解：(https://www.bilibili.com/video/BV12V4y1V73A/)

在 candidates[i] == candidates[i - 1] 相同的情况下：

used[i - 1] == true，说明同一树枝 candidates[i - 1] 使用过
used[i - 1] == false，说明同一树层 candidates[i - 1] 使用过

131 分割回文串

题目链接/文章讲解：(https://programmercarl.com/0131.分割回文串.html)

视频讲解：(https://www.bilibili.com/video/BV1c54y1e7k6/)

public static List<List<String>> partition(String s) {  
    List<List<String>> result = new ArrayList<>();  
    List<String> string = new ArrayList<>();  
    partitionDFS(0, s, string, result);  
    return result;  
}  
  
private static void partitionDFS(int startIndex, String s, List<String> string, List<List<String>> result) {  
    if (startIndex >= s.length()) {  
        result.add(new ArrayList<>(string));  
    }  
  
    for (int i = startIndex; i < s.length(); i++) {  
        String substring = s.substring(startIndex, i + 1);  
        if (!isPartition(substring)) {  
            continue;  
        }  
        string.add(substring);  
        partitionDFS(i + 1, s, string, result);  
        string.remove(string.size() - 1);  
    }  
}  
  
/**  
 * 判断传入字符串是否为回文字符串  
 * @param substring 截取的字符串  
 * @return 结果  
 */  
private static boolean isPartition(String substring) {  
    for (int i = 0, j= substring.length() - 1; i < j; i++, j--) {  
        if (substring.charAt(i) != substring.charAt(j)) {  
            return false;  
        }  
    }  
    return true;  
}

// 优化版 动态规划法
class Solution {
    List<List<String>> result;
    LinkedList<String> path;
    boolean[][] dp;

    public List<List<String>> partition(String s) {
        result = new ArrayList<>();
        char[] str = s.toCharArray();
        path = new LinkedList<>();
        dp = new boolean[str.length + 1][str.length + 1];
        isPalindrome(str);
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String str, int startIndex) {
        if (startIndex >= str.length()) {
            //如果起始位置大于s的大小，说明找到了一组分割方案
            result.add(new ArrayList<>(path));
        } else {
            for (int i = startIndex; i < str.length(); ++i) {
                if (dp[startIndex][i]) {
                    //是回文子串，进入下一步递归
                    //先将当前子串保存入path
                    path.addLast(str.substring(startIndex, i + 1));
                    //起始位置后移，保证不重复
                    backtracking(str, i + 1);
                    path.pollLast();
                } else {
                    //不是回文子串，跳过
                    continue;
                }
            }
        }
    }

    //通过动态规划判断是否是回文串,参考动态规划篇 52 回文子串
    public void isPalindrome(char[] str) {
        for (int i = 0; i <= str.length; ++i) {
            dp[i][i] = true;
        }
        for (int i = 1; i < str.length; ++i) {
            for (int j = i; j >= 0; --j) {
                if (str[j] == str[i]) {
                    if (i - j <= 1) {
                        dp[j][i] = true;
                    } else if (dp[j + 1][i - 1]) {
                        dp[j][i] = true;
                    }
                }
            }
        }
    }
}