组合总和
题解:
此题和前面的组合问题不同之处是,可以重复取同一个数字,不限制
1.递归函数的参数
题目给定的集合candidates以及目标值target,题目中是在求和,参数sum_, 记录遍历位置的参数startindex,
2.终止条件
当和sum_大于target以及等于的时候终止继续向下遍历,不过等于的情况需要收集结果
3.单层遍历逻辑
横向依然for循环遍历,每次都将集合candidates中的值进行相加,并放入到path中,但是递归的时候不同之处在于,startindex处,不再加一
代码:
组合总和ii
题解:
此题和之前的题目有个区别就是,给定的集合中有重复的数字,那就涉及到去重的问题,当然同一个数字也只能使用一次,在此我们使用一个数组used来去重,长度和集合长度相等
1.方法的参数
题目中给定的集合以及目标值target,因为要求的是和,所以需要传入一个和sum_,以及记录遍历位置的startindex,还有就是used
2.终止条件
就是和sum_大于target,以及等于target时终止,当然等于的情况是收集满足的结果
3.单层搜索逻辑
要去重的是“同一树层上使用过”,如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == False,就说明:前一个树枝,使用了 candidates[i - 1] ,也就是说同一树层使用过candidates[i - 1] 。此时就continue
代码:
分割回文串
题解:
切割问题类似为组合问题:
例如:abcdef
组合问题:选取一个a后,在bcdef中再去选取第二个,选取b之后再选取第三个
切割问题:切割一个a之后,在bcdef中再去切割第二段,切割b之后再切割第三段
抽象成一棵树形结构
1.递归函数参数
题目中给定的字符串,记录切割的位置的startindex
当然还有path,以及结果集result
2.终止条件
切割都了字符串的最后面,找到了一种切割方法,那就是终止,也就是startindex == len(s)
3.单层搜索逻辑
在此有个判断回文的,什么是回文,就是从前往后,从后向前,前后对应的元素相等,则为回文
我们遍历的是整个字符串
代码: