组合总和

剪枝优化 ：其实如果已经知道下一层的sum会大于target，就没有必要进入下一层递归了。

那么可以在for循环的搜索范围上做做文章了。

对总集合排序之后，如果下一层的sum（就是本层的 sum + candidates[i]）已经大于target，就可以结束本轮for循环的遍历。

List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum(int[] candidates, int target) {Arrays.sort(candidates);backtracking(candidates,target,0,0);return result;}public void backtracking(int[] candidates,int target,int sum,int startIndex){if (sum>target){return;}if (sum == target){result.add(new LinkedList<>(path));return;}for (int i = startIndex; i < candidates.length; i++) {path.add(candidates[i]);sum += candidates[i];backtracking(candidates,target,sum,i);sum -= candidates[i];path.removeLast();}}

---

组合总和II

解题思路：

1. 排序：首先对候选数组 candidates 进行排序，这样可以方便后续剪枝操作，同时也可以更容易地跳过重复的数字。
2. 回溯搜索：使用回溯法进行搜索。从根节点开始，每次向下搜索时，都要做出选择（选择当前数字或不选择当前数字），直到找到和为 target 的组合或者和超过 target 时回溯。
3. 剪枝：在搜索过程中，如果当前的和已经大于 target，则无需继续搜索，直接返回。
4. 跳过重复：由于数组已经排序，相同的数字会相邻，因此在搜索时，如果当前数字与前一个数字相同，并且前一个数字没有被使用过，则跳过当前数字，以避免产生重复的组合。
5. 记录结果：当找到一个有效的组合时，将其记录下来。

去重：设置一个数组来映射原数组，当前元素使用过，另新数组对应位置的值为1。
都知道组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。

强调一下，树层去重的话，需要对数组排序！

class Solution {List<List<Integer>> result = new ArrayList<>();LinkedList<Integer> path = new LinkedList<>();public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates);boolean[] used = new boolean[candidates.length];Arrays.fill(used,false);backtracking(candidates,target,0,0,used);return result;}public void backtracking(int[] candidates, int target,int sum,int stateIndex,boolean[] used){if (sum>target){return;}if (sum == target){result.add(new ArrayList<>(path));}for (int i = stateIndex; i < candidates.length; i++) {if (i>0&&candidates[i-1]==candidates[i]&&used[i-1]==false){//重要，按层去重continue;}path.add(candidates[i]);sum += candidates[i];used[i] = true;backtracking(candidates,target,sum,i+1,used);path.removeLast();sum -= candidates[i];used[i] = false;}}
}

---

分割回文串

解题步骤：

1. 定义回文串：首先需要一个辅助函数来判断一个字符串是否是回文串。
2. 回溯搜索：使用回溯算法来尝试所有可能的分割方式。
3. 剪枝优化：在搜索过程中，如果当前子串不是回文串，则不需要继续搜索下去。
4. 收集结果：当搜索到一个有效的分割方案时，将其加入到结果集中。

class Solution {List<List<String>> result = new ArrayList<>();LinkedList<String> path = new LinkedList<>();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 ArrayList<>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s,startIndex,i)){String a = s.substring(startIndex,i+1);path.add(a);}else {continue;}backtracking(s,i+1);path.removeLast();}}boolean isPalindrome(String s,int start,int end){for (int i = start,j = end; i <j ; i++,j--) {if (s.charAt(i)!=s.charAt(j)){return false;}}return true;}
}