本篇文章为你整理了LeetCode 39. 组合总和 40.组合总和II 131.分割回文串（组合汇总）的详细内容，包含有组合分割法 组合汇总 组合的总和 组合分类算法 LeetCode 39. 组合总和 40.组合总和II 131.分割回文串，希望能帮助你了解 LeetCode 39. 组合总和 40.组合总和II 131.分割回文串。
欢迎关注个人公众号：爱喝可可牛奶
LeetCode 39. 组合总和 40.组合总和II 131.分割回文串
LeetCode 39. 组合总和
回溯可看成对二叉树节点进行组合枚举，分为横向和纵向
每次往sum添加新元素时，必须明确从can哪个位置开始，定义变量pos
返回条件 sum == target 或 sum target; 横向结束条件 没有新元素可以添加了即pos can.length;
bt(can, sum, tar, pos){
if(sum == tar) add return;
if(sum tar) pos++ return;
for(int i = pos; i can.len;i++){
sum+=can[pos];
bt(can, sum, tar, i);
sum-=can[pos];
这个回溯考虑sum tar时， pos++不应该写在第3行，这样导致回溯减掉的元素值与递归添加的不一样。而应该放在第4行for()中，只有当纵向回溯结束时(也就是很多个sum+=can[i]导致return后)，横向遍历才会往右移动；回溯第n个can[i] 回溯第n-1个can[i];
一次回溯只能抵消一层递归；每次return只是从已经添加进sum的众多can[i]中减掉一个
举个栗子：
sum+= n个can[i]，回溯一次还剩n-1个can[i];这时要i++了；但是剩下的sum和这个i++后的新can[i]加起来可能也会超过tar，这步操作可以剪枝，避免进入新can[i]的递归；
for (int i = pos; i candidates.size() sum + candidates[i] = target; i++)
class Solution {
List List Integer res = new ArrayList ();
LinkedList Integer path = new LinkedList();
public List List Integer combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); // 先进行排序
backtracking(candidates, target, 0, 0);
return res;
public void backtracking(int[] candidates, int target, int sum, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new ArrayList (path));
return;
for (int i = idx; i candidates.length; i++) {
// 如果 sum + candidates[i] target 就终止遍历
if (sum + candidates[i] target) break;
path.add(candidates[i]);
backtracking(candidates, target, sum + candidates[i], i);
path.removeLast(); // 回溯，移除路径 path 最后一个元素
LeetCode 40.组合总和II
在原有基础上设限每个数字在每个组合中只能使用 一次 且不包含重复的组合
Arrays升序；纵向遍历时就要i++；Set去重
Set去重超时了！！！ 要在添加集合的时候就判断是否重复，取res中最后一个path和当前满足条件的path比较 也不行
纵向递归不需要去重，横向递归时采用去重
class Solution {
List List Integer res = new LinkedList();
LinkedList Integer path = new LinkedList();
int sum = 0;
public List List Integer combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // 先进行排序
backtracking(candidates, target, 0);
return res;
public void backtracking(int[] candidates, int target, int idx) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new LinkedList (path));
return;
for (int i = idx; i candidates.length sum + candidates[i] = target; i++) {
// 要对横向遍历时使用过的元素进行跳过 因为一样的元素在深度递归时已经把包含此元素的所有可能结果全部枚举过了
if (i idx candidates[i] == candidates[i - 1]) {
continue;
path.add(candidates[i]);
sum += candidates[i];
//System.out.println("sum="+sum);
//i++;
backtracking(candidates, target, i+1);
//i--;
//sum -= candidates[i];
sum-=path.getLast();
path.removeLast(); // 回溯，移除路径 path 最后一个元素
LeetCode 131.分割回文串
切割子串，保证每个子串都是 回文串
找到所有的子串组合，判断子串是否是回文串，根据索引切割 startIndex endIndex if(start-end) is ; res.add
class Solution {
List List String res = new ArrayList ();
LinkedList String path = new LinkedList ();
public List List String partition(String s) {
backTracking(s, 0);
return res;
private void backTracking(String s, int startIndex) {
//如果起始位置大于s的大小，说明找到了一组分割方案
if (startIndex = s.length()) {
res.add(new ArrayList(path));
return;
for (int i = startIndex; i s.length(); i++) {
//如果是回文子串，则记录
if (isPalindrome(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
path.add(str);
} else {
continue;
//起始位置后移，保证不重复
backTracking(s, i + 1);
// 一定要有回溯 开始下一种分割
path.removeLast();
//判断是否是回文串
private boolean isPalindrome(String s, int startIndex, int end) {
for (int i = startIndex, j = end; i i++, j--) {
if (s.charAt(i) != s.charAt(j)) {
return false;
return true;
题目给定的数据集如果使用数组的方式，要判断是否有序，没有说明有序最好视情排序
回溯横向移动的时机一定是某个纵向递归结束
看清题目要求，将串的所有子串都分割成回文子串
横向遍历逻辑 纵向递归startIndex++逻辑 回溯逻辑
以上就是LeetCode 39. 组合总和 40.组合总和II 131.分割回文串（组合汇总）的详细内容，想要了解更多 LeetCode 39. 组合总和 40.组合总和II 131.分割回文串的内容，请持续关注盛行IT软件开发工作室。
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。