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);}}}
}
