本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制

题目链接/文章讲解：代码随想录

视频讲解：带你学透回溯算法-组合总和（对应「leetcode」力扣题目：39.组合总和）| 回溯法精讲！_哔哩哔哩_bilibili

本题开始涉及到一个问题了：去重。

注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。

题目链接/文章讲解：代码随想录

题解思路：

本题主要在于去重条件操作的理解，这很重要！！！然后就是整体思路和求组合问题差不多，具体的去重操作理解可以分成两种：树层去重和树枝去重，以本题结合代码注释为例说明如下：
第一种树层去重：used[i - 1] == false --> 说明此时第一轮递归已经结束了，此时整个if语句的判断条件意思是：当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时，直接跳过此轮递归，因为之前那一轮已经包括了所有种以1开头的组合；
第二种树枝去重：used[i - 1] == true --> 说明此时还在第一轮里面，此时整个if语句的判断条件意思是：当在第一轮搜索所有的组合过程中，如果遇到和前一个元素相同时，直接跳过相邻元素相同组合的搜索，这就意味着不会出现 [ 1 1 6]这种组合了，显然是错误的
最后想分享的就是，可以多看卡哥视频讲解的思路，再自己好好去理解这两种情况！！！

class Solution {LinkedList<Integer> path = new LinkedList<>();List<List<Integer>> result = new ArrayList<>();int sum = 0;boolean[] used;public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); //先对数组进行排序used = new boolean[candidates.length]; //定义一个和给定数组相同大小、具有标记功能的数组Arrays.fill(used, false); //使用used数组标记之前是否使用过元素，0表示未使用过，1表示使用过backtracking(candidates, target, 0);return result;}public void backtracking(int[] candidates, int target, int start){if(sum > target) return;if(sum == target){result.add(new LinkedList<Integer>(path));return;}for(int i = start; i < candidates.length; i++){if(i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) continue; //used[i - 1] == false：树层去重操作；used[i - 1] == true：树枝去重操作//这里可以这么去理解这种判断条件：（以第一轮和第二轮递归说明，给定的排序后的数组为[1 1 2 5 6 7]，target = 8）//used[i - 1] == false --> 说明此时第一轮递归已经结束了，此时整个if语句的判断条件意思是：当第二轮开始递归的开头元素和第一轮开始的递归的开头元素相同时，直接跳过此轮递归，因为之前那一轮已经包括了所有种以1开头的组合；//used[i - 1] == true --> 说明此时还在第一轮里面，此时整个if语句的判断条件意思是：当在第一轮搜索所有的组合过程中，如果遇到和前一个元素相同时，直接跳过相邻元素相同组合的搜索，这就意味着不会出现 [ 1 1 6]这种组合了，显然是错误的used[i] = true;path.add(candidates[i]);sum += candidates[i];backtracking(candidates, target, i + 1);used[i] = false; //递归之后一定要回溯，这是不能忘的！把之前使用过的元素重新都标记为0，开始下一次的递归搜索path.removeLast();sum -= candidates[i];}}
}

class Solution {LinkedList<String> path = new LinkedList<>();List<List<String>> result = new ArrayList<>();public List<List<String>> partition(String s) {backtracking(s, 0);return result;}public void backtracking(String s, int startIndex){if(startIndex >= s.length()){ result.add(new LinkedList<String>(path));return;}for(int i = startIndex; i < s.length(); i++){if(isPalindrome(s, startIndex, i)){ //如果索引的范围内的子串是回文串，则直接切割子串及时添加到path路径里面，这里使用下标直接进行切割数组的操作，不用装到容器里面判断String temp = s.substring(startIndex, i + 1); //startIndex是固定不变的，而i会在每轮递归的时候都会进行i++操作，主要substring(start,end)是左闭右开的path.add(temp);}else{continue;}backtracking(s, i + 1); //下一轮递归的时候i = i+1, 保证不会重复切割path.removeLast();}}public boolean isPalindrome(String s, int startIndex, int end){for(int i = startIndex, j = end; i < j; i++, j--){if(s.charAt(i) != s.charAt(j)){return false;}}return true;}}