组合总和
其实总的思路和前面几类组合问题区别不大
本题由于说明了元素可以重复选取 且无需考虑sum为0的情况
只需要把边界的startIndex迭代从i + 1 变成 i 即可
i表示可以选取元素本身
很容易写出以下未进行剪枝的代码
剪枝情况只是多了一种 也就是sum + 下一个候选元素 ＞ target的时候直接略过本次循环 这里需要对候选数组进行排序
组合总和 II
本题和Ⅰ的区别就是这里不能选取同样的元素 也就是需要进行去重操作
重点在于这个使用的used数组 首先candidates需要进行排序 然后used全部初始化为false
这样我们在选取元素的时候 把它置为true 在我们回溯的时候置为false
实际上这样表示了 在同一个枝条下进行递归时 选择了的元素是始终为true的 如果candidate[i] == candidate[i - 1]也没有关系
因为这里实际上说明了candidate数组有重复元素 我们只不过只能使用一次而已 表现在used数组就是used[i - 1]是true
但是如果发现used[i - 1]是false 并且 candidate[i] == candidate[i - 1] 这就说明我们使用了同个元素两遍
这个去重操作是本题的难点
以下是不用used数组直接利用下标进行去重
分割回文串
对字符串操作要熟悉
这里还有顺便考察了一下回文串的判断
利用双指针前后比较就很快写出来
实际是和前面组合是一个思路
这里还不需要考虑去重
