组合总和

视频讲解带你学透回溯算法-组合总和对应「leetcode」力扣题目39.组合总和|

回溯法精讲_哔哩哔哩_bilibili

这是基本的回溯算法求组合问题的代码思路没有什么问题能ac就是说记录第一次不看题解写题思想就是暴力算法的本质剪枝条件的优化套路其实差不多这里就是多了一个先对数组进行升序排序的操作好更加有利于剪枝条件作判断

class

//使用Arrays工具类对给定的数组先按升序排列好让回溯方法里面的剪枝条件作快速判断backtracking(candidates,target,0);return

result;}public

//先对数组进行升序排序可以更加对其作判断不加也没事就是说if(sum

LinkedListInteger(path));return;}for(int

satart;

candidates[i];backtracking(candidates,target,i);

//这里是i因为避免取到重复的组合path.removeLast();sum

candidates[i];}}

本题主要在于去重条件操作的理解这很重要然后就是整体思路和求组合问题差不多具体的去重操作理解可以分成两种树层去重和树枝去重以本题结合代码注释为例说明如下第一种树层去重used[i

false

说明此时第一轮递归已经结束了此时整个if语句的判断条件意思是当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时直接跳过此轮递归因为之前那一轮已经包括了所有种以1开头的组合第二种树枝去重used[i

true

说明此时还在第一轮里面此时整个if语句的判断条件意思是当在第一轮搜索所有的组合过程中如果遇到和前一个元素相同时直接跳过相邻元素相同组合的搜索这就意味着不会出现

最后想分享的就是可以多看卡哥视频讲解的思路再自己好好去理解这两种情况

class

//定义一个和给定数组相同大小、具有标记功能的数组Arrays.fill(used,

false);

//使用used数组标记之前是否使用过元素0表示未使用过1表示使用过backtracking(candidates,

target,

LinkedListInteger(path));return;}for(int

start;

true树枝去重操作//这里可以这么去理解这种判断条件以第一轮和第二轮递归说明给定的排序后的数组为[1

7]target

说明此时第一轮递归已经结束了此时整个if语句的判断条件意思是当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时直接跳过此轮递归因为之前那一轮已经包括了所有种以1开头的组合//used[i

true

说明此时还在第一轮里面此时整个if语句的判断条件意思是当在第一轮搜索所有的组合过程中如果遇到和前一个元素相同时直接跳过相邻元素相同组合的搜索这就意味着不会出现

true;path.add(candidates[i]);sum

candidates[i];backtracking(candidates,

target,

//递归之后一定要回溯这是不能忘的把之前使用过的元素重新都标记为0开始下一次的递归搜索path.removeLast();sum

candidates[i];}}

本题还是有难度的需要把切割的动作抽象成组合的问题多看卡哥视频里面讲解的思路捋清之后再下手写执行代码卡哥里面说的思路还是很清楚的多品味品味就好代码具体注意的事项看注释如何把切割动作抽象成组合问题卡哥视频说的很详细移动到卡哥视频就行

class

LinkedListString(path));return;}for(int

startIndex;

//如果索引的范围内的子串是回文串则直接切割子串及时添加到path路径里面这里使用下标直接进行切割数组的操作不用装到容器里面判断String

temp

//startIndex是固定不变的而i会在每轮递归的时候都会进行i操作主要substring(start,end)是左闭右开的path.add(temp);}else{continue;}backtracking(s,

1);

保证不会重复切割path.removeLast();}}public

boolean