歡迎關(guān)注個人公眾號：愛喝可可牛奶
LeetCode 39. 組合總和 40.組合總和II 131.分割回文串
LeetCode 39. 組合總和
分析
回溯可看成對二叉樹節(jié)點進行組合枚舉甸怕，分為橫向和縱向
每次往sum添加新元素時，必須明確從can哪個位置開始摊滔，定義變量pos
返回條件 sum == target 或 sum > target; 橫向結(jié)束條件 沒有新元素可以添加了即pos<can.length;
bt(can, sum, tar, pos){
if(sum == tar) add return;
if(sum > tar) pos++ return;
for(int i = pos; i < can.len;i++){
sum+=can[pos];
bt(can, sum, tar, i);
sum-=can[pos];
}
}
這個回溯考慮sum > tar時， pos++不應(yīng)該寫在第3行，這樣導(dǎo)致回溯減掉的元素值與遞歸添加的不一樣箱靴。而應(yīng)該放在第4行for()中鬼佣，只有當縱向回溯結(jié)束時(也就是很多個sum+=can[i]導(dǎo)致return后)垛叨，橫向遍歷才會往右移動；回溯第n個can[i] 回溯第n-1個can[i];
剪枝
一次回溯只能抵消一層遞歸装畅；每次return只是從已經(jīng)添加進sum的眾多can[i]中減掉一個
舉個栗子：
sum+= n個can[i]靠娱，回溯一次還剩n-1個can[i];這時要i++了；但是剩下的sum和這個i++后的新can[i]加起來可能也會超過tar掠兄，這步操作可以剪枝像云，避免進入新can[i]的遞歸锌雀；
for (int i = pos; i < candidates.size() && sum + candidates[i] <= target; i++)
代碼
class Solution {
List<List<Integer>> res = 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 res;
}
public void backtracking(int[] candidates, int target, int sum, int idx) {
// 找到了數(shù)字和為 target 的組合
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = idx; i < candidates.length; i++) {
// 如果 sum + candidates[i] > target 就終止遍歷
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
backtracking(candidates, target, sum + candidates[i], i);
path.removeLast(); // 回溯，移除路徑 path 最后一個元素
}
}
}
LeetCode 40.組合總和II
分析
在原有基礎(chǔ)上設(shè)限每個數(shù)字在每個組合中只能使用 一次 且不包含重復(fù)的組合
Arrays升序迅诬；縱向遍歷時就要i++腋逆；Set去重
Set去重超時了！３薮惩歉！ 要在添加集合的時候就判斷是否重復(fù)，取res中最后一個path和當前滿足條件的path比較 也不行
縱向遞歸不需要去重俏蛮，橫向遞歸時采用去重
剪枝
代碼
class Solution {
List<List<Integer>> res = new LinkedList();
LinkedList<Integer> path = new LinkedList();
int sum = 0;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates); // 先進行排序
backtracking(candidates, target, 0);
return res;
}
public void backtracking(int[] candidates, int target, int idx) {
// 找到了數(shù)字和為 target 的組合
if (sum == target) {
res.add(new LinkedList<>(path));
return;
}
for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
// 要對橫向遍歷時使用過的元素進行跳過 因為一樣的元素在深度遞歸時已經(jīng)把包含此元素的所有可能結(jié)果全部枚舉過了
if (i > idx && candidates[i] == candidates[i - 1]) {
continue;
}
path.add(candidates[i]);
sum += candidates[i];
//System.out.println("sum="+sum);
//i++;
backtracking(candidates, target, i+1);
//i--;
//sum -= candidates[i];
sum-=path.getLast();
path.removeLast(); // 回溯撑蚌，移除路徑 path 最后一個元素
}
}
}
LeetCode 131.分割回文串
分析
切割子串，保證<u>每個子串都是 回文串</u>
找到所有的子串組合搏屑，判斷子串是否是回文串锨并，根據(jù)索引切割 startIndex endIndex if(start-end) is ; res.add
代碼
class Solution {
List<List<String>> res = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return res;
}
private void backTracking(String s, int startIndex) {
//如果起始位置大于s的大小，說明找到了一組分割方案
if (startIndex >= s.length()) {
res.add(new ArrayList(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;
}
//起始位置后移第煮，保證不重復(fù)
backTracking(s, i + 1);
// 一定要有回溯 開始下一種分割
path.removeLast();
}
}
//判斷是否是回文串
private 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;
}
}
總結(jié)
- 題目給定的數(shù)據(jù)集如果使用數(shù)組的方式，要判斷是否有序抑党，沒有說明有序最好視情排序
- 回溯橫向移動的時機一定是某個縱向遞歸結(jié)束
- 看清題目要求包警，將串的所有子串都分割成回文子串
- 橫向遍歷邏輯 縱向遞歸startIndex++邏輯 回溯邏輯
本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布！
