歡迎關(guān)注個(gè)人公眾號(hào)：愛喝可可牛奶
LeetCode 39. 組合總和 40.組合總和II 131.分割回文串
LeetCode 39. 組合總和
分析
回溯可看成對(duì)二叉樹節(jié)點(diǎn)進(jìn)行組合枚舉，分為橫向和縱向
每次往sum添加新元素時(shí)，必須明確從can哪個(gè)位置開始，定義變量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];
}
}
這個(gè)回溯考慮sum > tar時(shí)， pos++不應(yīng)該寫在第3行，這樣導(dǎo)致回溯減掉的元素值與遞歸添加的不一樣。而應(yīng)該放在第4行for()中，只有當(dāng)縱向回溯結(jié)束時(shí)(也就是很多個(gè)sum+=can[i]導(dǎo)致return后)，橫向遍歷才會(huì)往右移動(dòng)；回溯第n個(gè)can[i] 回溯第n-1個(gè)can[i];
剪枝
一次回溯只能抵消一層遞歸；每次return只是從已經(jīng)添加進(jìn)sum的眾多can[i]中減掉一個(gè)
舉個(gè)栗子：
sum+= n個(gè)can[i]，回溯一次還剩n-1個(gè)can[i];這時(shí)要i++了；但是剩下的sum和這個(gè)i++后的新can[i]加起來可能也會(huì)超過tar，這步操作可以剪枝，避免進(jìn)入新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); // 先進(jìn)行排序
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 最后一個(gè)元素
}
}
}
LeetCode 40.組合總和II
分析
在原有基礎(chǔ)上設(shè)限每個(gè)數(shù)字在每個(gè)組合中只能使用 一次 且不包含重復(fù)的組合
Arrays升序；縱向遍歷時(shí)就要i++；Set去重
Set去重超時(shí)了?。?！ 要在添加集合的時(shí)候就判斷是否重復(fù)，取res中最后一個(gè)path和當(dāng)前滿足條件的path比較 也不行
縱向遞歸不需要去重，橫向遞歸時(shí)采用去重
剪枝
代碼
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); // 先進(jìn)行排序
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++) {
// 要對(duì)橫向遍歷時(shí)使用過的元素進(jìn)行跳過 因?yàn)橐粯拥脑卦谏疃冗f歸時(shí)已經(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 最后一個(gè)元素
}
}
}
LeetCode 131.分割回文串
分析
切割子串，保證<u>每個(gè)子串都是 回文串</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ù)組的方式，要判斷是否有序，沒有說明有序最好視情排序
- 回溯橫向移動(dòng)的時(shí)機(jī)一定是某個(gè)縱向遞歸結(jié)束
- 看清題目要求，將串的所有子串都分割成回文子串
- 橫向遍歷邏輯 縱向遞歸startIndex++邏輯 回溯邏輯
本文由博客一文多發(fā)平臺(tái) OpenWrite 發(fā)布！
