39.組合總和

給你一個 無重復元素 的整數數組 candidates 和一個目標整數 target ，找出 candidates 中可以使數字和為目標數 target 的 所有 不同組合 ，并以列表形式返回。你可以按 任意順序 返回這些組合。

candidates 中的 同一個 數字可以 無限制重復被選取 。如果至少一個數字的被選數量不同，則兩種組合是不同的。

對于給定的輸入，保證和為 target 的不同組合數少于 150 個。

示例 1：輸入：candidates = [2,3,6,7], target = 7
輸出：[[2,2,3],[7]]
解釋：
2 和 3 可以形成一組候選，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一個候選， 7 = 7 。
僅有這兩種組合。
示例 2：輸入: candidates = [2,3,5], target = 8
輸出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：輸入: candidates = [2], target = 1
輸出: []

注意candidates中的數字可以無限次重復被讀取
還是和回溯法模板一樣，全局變量path和res。需要一個startIndex控制for循環的起始位置。
什么時候需要startIndex：一個集合求組合（例如昨天的兩道題）
多個集合求組合就不需要startIndex（電話號碼）

每個數字可以重復利用：startIndex每次不用+1。

優化：如果在for循環中剪枝，就需要對數組先進行排序，這樣如果sum+candidates[i]>target，那么后面的i肯定也都不符合條件。

class Solution {List<Integer> path;List<List<Integer>> res;int[] candidates;public List<List<Integer>> combinationSum(int[] candidates, int target) {path = new ArrayList<>();res = new ArrayList<>();this.candidates = candidates;Arrays.sort(this.candidates);backtracking(target, 0, 0);return res;}void backtracking(int target, int sum, int startIndex) {// if (target < sum) {//     return;// }if (target == sum) {res.add(new ArrayList<Integer>(path));return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {path.add(candidates[i]);sum += candidates[i];backtracking(target, sum, i);sum -= candidates[i];path.remove(path.size() - 1);}}
}

40.組合總和II

給定一個候選人編號的集合 candidates 和一個目標數 target ，找出 candidates 中所有可以使數字和為 target 的組合。

candidates 中的每個數字在每個組合中只能使用 一次 。

注意：解集不能包含重復的組合。

示例 1:輸入: candidates = [10,1,2,7,6,1,5], target = 8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:輸入: candidates = [2,5,2,1,2], target = 5,
輸出:
[
[1,2,2],
[5]
]

數字可以重復，但是不能超過在candicates中出現的次數。比如candidates有兩個1，那結果集合不能超過2個1。
所以在上一題的基礎上，需要引入一個布爾數組used，標志每個candidates中的數是否被使用了（加入了path）。
Java初始化boolean數組都是false。
回溯函數同樣需要index，但是因為candidates中的值不能重復，所以繼續回溯還是要i+1。

去重：
同一樹枝使用過：同一樹枝上的元素都是一個組合里的元素（path），不用去重
同一樹層使用過：需要去重，去重前還要先對數組排序。同一樹層上相同兩個重復元素不能重復選取。所以判斷條件就是candidates[i-1]==candidates[i]&&used[i-1]==false。used[i-1]是false說明了i-1元素在上一次回溯使用過，所以不能再選。

class Solution {int[] candidates;List<List<Integer>> res;List<Integer> path;public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 樹層去重需要對數組排序this.candidates = candidates;res = new ArrayList<>();path = new ArrayList<>();boolean[] used = new boolean[candidates.length];backtracking(target, 0, 0, used);return res;}void backtracking(int target, int sum, int startIndex, boolean[] used) {if (sum == target) {res.add(new ArrayList<Integer>(path));return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {if (i > 0 && candidates[i - 1] == candidates[i] && used[i - 1] == false) {continue;}sum += candidates[i];path.add(candidates[i]);used[i] = true;backtracking(target, sum, i + 1, used);used[i] = false;path.remove(path.size() - 1);sum -= candidates[i];}}
}

131.分割回文串

給你一個字符串 s，請你將 s 分割成一些 子串，使每個子串都是 回文串 。返回 s 所有可能的分割方案。

示例 1：輸入：s = "aab"
輸出：[["a","a","b"],["aa","b"]]
示例 2：輸入：s = "a"
輸出：[["a"]]

切割問題也類似組合問題，可以使用排序解決。需要一個startIndex標志每次分割開始的位置。
backtracking終止條件：startIndex>=s.length() startIndex已經走到了字符串末尾，說明分割完了
for循環從startIndex的位置開始遍歷，每次判斷[startIndex,i]子串（閉區間）是否是回文串，如果是，就分割，然后下次回溯從i+1開始。

class Solution {List<String> path;List<List<String>> res;public List<List<String>> partition(String s) {path = new ArrayList<>();res = new ArrayList<>();backtracking(s, 0);return res;}public void backtracking(String s, int startIndex) {if (startIndex >= s.length()) {res.add(new ArrayList<String>(path));return;}for (int i = startIndex; i < s.length(); i++) {if (isPalindrome(s, startIndex, i)) {String str = s.substring(startIndex, i + 1);path.add(str);} else {continue;}backtracking(s, i + 1);path.remove(path.size() - 1);}}public boolean isPalindrome(String s, int begin, int end) {while (begin < end) {if (s.charAt(begin) != s.charAt(end)) {return false;}begin++;end--;}return true;}
}