39. 组合总和
画出决策图。每次都从待选择集合中拿出一个元素放进 path，并累加进 sum，然后递归做出第二次决策。对于每一次决策，如果 sum == target，则得到一个解，并放进结果集。因为这次要求 path 中可选择重复的元素，例如 target 为 4，path 可以是 [1, 1, 1, 1]，因此每次决策中 for 的起始下标（startIndex）可以和上次决策中的一致。
又因为求的是组合问题。[1, 2, 3] 和 [2, 1, 3] 是一样的，因此需要控制 for 的起始遍历顺序，于是引入了 startIndex 变量。
举个例子，假设 target 是 4，第一次第一层决策选择了 1，那么产生的结果有 [1, 1, 1, 1]，[1, 1, 2]，[1, 2, 1]，[1, 3]，第二次第一层决策时选择了 2，那么第二次第二层决策就不能选择 1，因为第一次决策时已经把 1、2 的情况讨论过了，该有的解都有了，再来一遍就会重复，因此后续的几次决策要把前面做决策的值排除掉，所以组合问题一般需要 for 循环从指定的位置开始遍历，即 startIndex。
class Solution {
private List<List<Integer>> res;
private LinkedList<Integer> path;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
res = new LinkedList<>();
path = new LinkedList<>();
backtrace(candidates, target, 0);
return res;
}
public void backtrace(int[] candidates, int target, int startIndex) {
// 下面有优化，这里就不需要了
// if (target < 0) return;
if (target == 0) {
// 找到一个解
res.add(new LinkedList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
// 优化手段1：已知当前数值相加会大于 target，就没必要进入下一次递归了（虽然下一次递归会立刻返回，但是会多一层递归）
// 优化手段2：如果 candidates 是个有序数组，那么当遇到当前数值相加大于 target 时，后续的数值就不需要考虑了，直接 break，更省事
if (target - candidates[i] < 0) continue;
path.add(candidates[i]);
backtrace(candidates, target - candidates[i], i);
path.removeLast();
}
}
}40. 组合总和 II
class Solution {
private List<List<Integer>> res;
private LinkedList<Integer> path;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
res = new LinkedList<>();
path = new LinkedList<>();
// 去重的关键 1
// 剪枝的关键
Arrays.sort(candidates);
backtrace(candidates, target, 0);
return res;
}
public void backtrace(int[] candidates, int target, int startIndex) {
// if (target < 0) return;
if (target == 0) {
res.add(new LinkedList<>(path));
return;
}
// 剪枝
for (int i = startIndex; i < candidates.length && target - candidates[i] >= 0; i++) {
// 去重的关键 2
if (i > startIndex && candidates[i] == candidates[i - 1]) continue;
path.add(candidates[i]);
backtrace(candidates, target - candidates[i], i + 1);
path.removeLast();
}
}
}131. 分割回文串
这道题一开始没理解到底要怎样分割，看了 Carl 的解释才知道和组合的方式差不多。例如字符串是 “aab”，一开始切分第一个 “a”，是回文串，然后再切分剩下的字符串 “ab”，切分第二个 “a”，也是回文串，继续往下（递归）切分 “b”，发现也是回文串，此时切到底了，将这三个结果收集起来。然后第二次切就从第二个 “a” 开始，切出来的是 “aa”，是回文串，剩下 “b”，再切 “b”，也是回文串，切到底了，收集起来。然后第三次切就从 “b” 开始，切出来的是 “aab”，不是回文串，切到底了，结束。于是就有了答案：[["a","a","b"],["aa","b"]]。
private List<List<String>> res;
private LinkedList<String> path;
public List<List<String>> partition(String s) {
res = new LinkedList<>();
path = new LinkedList<>();
backtrace(s, 0);
return res;
}
public void backtrace(String s, int startIndex) {
if (startIndex >= s.length()) {
res.add(new LinkedList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
String str = s.substring(startIndex, i + 1);
// 是回文串，才加入 path，继续向下切分
if (isPalindrome(str)) {
path.add(str);
backtrace(s, i + 1);
path.removeLast();
}
}
}
public boolean isPalindrome(String s) {
int left = 0, right = s.length() - 1;
while (left < right) {
if (s.charAt(left) != s.charAt(right)) return false;
left++;
right--;
}
return true;
}何时使用 startIndex，何时不用
这里讲的用或不用指的是在 for 循环中 i 的初始化那里。
一般来说，如果是 组合 题目，且要求从一个集合里面做选择，就需要使用 startIndex，用于对最终结果的 去重。如果是排列的题目，允许有重复的序列，所以 for 循环中 i 的初始化从 0 开始，而不是 startIndex。