当前位置：首页 > article >正文

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

article 2024/11/14 11:11:09

39. 组合总和

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili关于回溯算法，我公众号里已经讲完了，并且将回溯算法专题整理成一本PDF，该PDF共5万字，包含了30多张树形结构图、15道力扣精选回溯题目，21篇回溯法精讲文章，由浅入深，绝对是全网最精良的回溯算法资料！关注公众号「代码随想录」后台回复：回溯算法，就可以获取了，赶快下载看一看吧, 视频播放量 87277、弹幕量 655、点赞数 1959、投硬币枚数 1654、收藏人数 511、转发人数 94, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！，回溯算法套路②组合型回溯+剪枝【基础算法精讲 15】，带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！，贪心算法理论基础！，【LeetCode 每日一题】40. 组合总和 II | 手写图解版思路 + 代码讲解，带你学透回溯算法（理论篇）| 回溯法精讲！，组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列，回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II，带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！，这就是传说中的N皇后？回溯算法安排！| LeetCode：51.N皇后https://www.bilibili.com/video/BV1KT4y1M7HJ

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

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

    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            path.add(candidates[i]);
            backtracking(candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1);
        }
    }
}

40.组合总和II

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详细题解，应有尽有！, 视频播放量 59586、弹幕量 966、点赞数 1899、投硬币枚数 1869、收藏人数 354、转发人数 101, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：还得用回溯算法！| LeetCode：17.电话号码的字母组合，带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！，回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II，贪心算法理论基础！，回溯算法解决子集问题，如何去重？| LeetCode：90.子集II，带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！，带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！，带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！，组合与排列的区别，回溯算法求解的时候，有何不同？| LeetCode：46.全排列，这就是传说中的N皇后？回溯算法安排！| LeetCode：51.N皇后https://www.bilibili.com/video/BV12V4y1V73A

思路：定义一个used数组来去重。去重主要是在数层上操作。如果used[i-1]==false&&candidates[i]==candidates[i-1]，那么说明是在树层上，直接跳过；而如果used[i-1]==true，说明在树枝上，加入path中。因为在递归指的是树枝，在递归中used的值为true，该树枝递归完毕后，把used变为false。以此来判断是树层还是树枝上。

class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    /*public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        backtracking(candidates, target, 0, 0);
        return result;

    }*/
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        boolean[] used = new boolean[candidates.length];
        backtracking(candidates, target, 0, 0, used);
        return result;
    }

    public void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used) {
        if (sum == target) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            if (sum + candidates[i] > target) {
                break;
            }
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.add(candidates[i]);
            used[i] = true;
            backtracking(candidates, target, sum + candidates[i], i + 1, used);
            path.remove(path.size() - 1);
            used[i] = false;
        }
    }
}

131.分割回文串

题目链接：. - 力扣（LeetCode）

文章讲解：代码随想录

视频讲解：带你学透回溯算法-分割回文串（对应力扣题目：131.分割回文串）| 回溯法精讲！_哔哩哔哩_bilibili关于回溯算法，我公众号里已经讲完了，并且将回溯算法专题整理成一本PDF，该PDF共5万字，包含了30多张树形结构图、15道力扣精选回溯题目，21篇回溯法精讲文章，由浅入深，绝对是全网最精良的回溯算法资料！关注公众号「代码随想录」后台回复：回溯算法，就可以获取了，赶快下载看一看吧, 视频播放量 92052、弹幕量 849、点赞数 2318、投硬币枚数 2057、收藏人数 497、转发人数 109, 视频作者代码随想录, 作者简介哈工大师兄，在腾讯、百度搬过砖，代码随想录网站：programmercarl.com，相关视频：带你学透回溯算法（理论篇）| 回溯法精讲！，带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！，贪心算法理论基础！，带你学透0-1背包问题！| 关于背包问题，你不清楚的地方，这里都讲了！| 动态规划经典问题 | 数据结构与算法，带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！，回溯算法套路①子集型回溯【基础算法精讲 14】，带你学透回溯算法-组合问题的剪枝操作（对应力扣题目：77.组合）| 回溯法精讲！，从此再也不怕动态规划了，动态规划解题方法论大曝光！| 理论基础 |力扣刷题总结| 动态规划入门，手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找，回溯算法精讲，树层去重与树枝去重 | LeetCode：491.递增子序列https://www.bilibili.com/video/BV1c54y1e7k6

思路：回溯切割字符串，动态规划先求出字符串区间i到j是否是回文串。

class Solution {
    List<List<String>> result = new ArrayList<>();
    List<String> path = new ArrayList<>();
    boolean[][] isPalindrome;

    public List<List<String>> partition(String s) {
        isPalindrome = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j >= 0; j--) {
                if (i == j) {
                    isPalindrome[i][j] = true;
                } else if (i - j == 1) {
                    isPalindrome[j][i] = (s.charAt(i) == s.charAt(j));
                } else {
                    isPalindrome[j][i] = ((s.charAt(i) == s.charAt(j)) && isPalindrome[j+1][i-1]);
                }
            }
        }
        backtracking(s, 0);
        return result;
    }

    public void backtracking(String s, int startIndex) {
        if (startIndex >= s.length()) {
            result.add(new ArrayList<>(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            if (isPalindrome[startIndex][i]) {
                path.add(s.substring(startIndex, i + 1));
                backtracking(s, i + 1);
                path.remove(path.size() - 1);
            }
        }

    }
}

查看全文

http://www.kler.cn/a/390937.html