一. 学习文章及资料
二. 学习内容
题目特点：
1.无重复元素的整数数组 candidates
2.同一个元素可以重复被选取
因为本题没有组合数量要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过target，就返回！而在77.组合 (opens new window)和216.组合总和III (opens new window)中都可以知道要递归K层，因为要取k个元素的组合
本题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？
如果是一个集合取组合，就需要startIndex，例如：77.组合 (opens new window)
如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合
注意本题和77.组合 (opens new window)、216.组合总和III (opens new window)的一个区别是：本题元素为可重复选取的。所以递归的时候传 i 而不是 i+1
backtracking(candidates,target,i); // 关键点:不用i+1了，表示可以重复读取当前的数class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
void backtracking(int[] candidates,int target,int starkIndex){
if(target==0){
result.add(new ArrayList(path));
return;
}
for(int i=starkIndex;i<candidates.length&&target-candidates[i]>=0;i++){
target-=candidates[i];
path.add(candidates[i]);
backtracking(candidates,target,i);
target+=candidates[i];
path.removeLast();
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates); //排序后才可以剪枝
backtracking(candidates,target,0);
return result;
}
}(1)题目特点：
1.集合有重复元素
2.集合每个元素只能使用一次
3.组合不能重复
与上一题不同的是集合有重复元素，且每个元素只能用一次
(2)题目思路：
每次选择都要受如下限制来剪枝
选过的不能再选（元素只能用一次）
不能产生重复组合
当和为 target，找到一个正确的解，加入解集。当和 > target，爆掉了，不用继续选了，结束当前递归，继续搜别的分支，找齐所有的解。还有一种方式采用的是减的方式，每次target都减去选择的数直到target为0，说明找到一个正确的数。target<0，说明超了。
因此，回到上一个节点，撤销当前选择的数字，去进入下一个分支。
(3)题目步骤:
1.给定的数组可能有重复的元素，先排序，使得重复的数字相邻，方便去重。
2.for 枚举出选项时，加入下面判断，从而忽略掉同一层重复的选项，避免产生重复的组合。比如[1,2,2,2,5]，选了第一个 2，变成 [1,2]，它的下一选项也是 2，跳过它，因为如果选它，就还是 [1,2]。
if (i > startIndex && candidates[i - 1] == candidates[i]) {
continue;
}
3.当前选择的数字不能和下一个选择的数字重复（每个元素只能用一次），给子递归传i+1，避免与当前选的i重复。
class Solution {
List<List<Integer>> result=new ArrayList<>();
List<Integer> path=new LinkedList<>();
void backtracking(int[] candidates,int target,int startIndex){
if(target<0){
return;
}
if(target==0){
result.add(new ArrayList(path));
return;
}
for(int i=startIndex;i<candidates.length;i++){
if(i>startIndex&&candidates[i]==candidates[i-1]){
continue;
}
path.add(candidates[i]);
target-=candidates[i];
backtracking(candidates,target,i+1);
target+=candidates[i];
path.removeLast();
}
return;
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates,target,0);
return result;
}
}(1)递归函数参数
全局变量数组path存放切割后回文的子串，二维数组result存放结果集。 （这两个参数可以放到函数参数里）
本题递归函数参数还需要startIndex，因为切割过的地方，不能重复切割，和组合问题也是保持一致的
(2)递归函数终止条件
从树形结构的图中可以看出：切割线切到了字符串最后面，说明找到了一种切割方法，此时就是本层递归的终止条件。
那么在代码里什么是切割线呢？
在处理组合问题的时候，递归参数需要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
(3)单层搜索的逻辑
来看看在递归循环中如何截取子串呢？
在 for(int i=startIndex;i<s.length();i++)循环中，我们 定义了起始位置startIndex，那么 [startIndex, i] 就是要截取的子串。
首先判断这个子串是不是回文，如果是回文，就加入在path中，path用来记录切割过的回文子串。
注意切割过的位置，不能重复切割，所以，backtracking(s, i + 1); 传入下一层的起始位置为i + 1。
(4)判断回文子串
可以使用双指针法，一个指针从前向后，一个指针从后向前，如果前后指针所指向的元素是相等的，就是回文字符串了。
class Solution {
List<List<String>> result=new ArrayList<>();
List<String> path=new LinkedList<>();
void backtracking(String s,int startIndex,StringBuilder sb){
if(startIndex==s.length()){
result.add(new ArrayList<>(path));
return;
}
for(int i=startIndex;i<s.length();i++){
sb.append(s.charAt(i));
if(cheak(sb)){ //如果是回文，划分并向下层继续搜索；分支不是回文跳过
path.add(sb.toString());
backtracking(s,i+1,new StringBuilder());
path.removeLast();
}
}
}
boolean cheak(StringBuilder sb){
for(int i=0;i<sb.length()/2;i++){
if(sb.charAt(i)!=sb.charAt(sb.length()-1-i)){
return false;
}
}
return true;
}
public List<List<String>> partition(String s) {
backtracking(s,0,new StringBuilder());
return result;
}
}