欢送关注集体公众号：爱喝可可牛奶
LeetCode 39. 组合总和 40.组合总和II 131.宰割回文串
LeetCode 39. 组合总和
剖析
回溯可看成对二叉树节点进行组合枚举，分为横向和纵向
每次往sum增加新元素时，必须明确从can哪个地位开始，定义变量pos
返回条件 sum == target 或 sum > target; 横向完结条件 没有新元素能够增加了即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++不应该写在第3行，这样导致回溯减掉的元素值与递归增加的不一样。而应该放在第4行for()中，只有当纵向回溯完结时(也就是很多个sum+=can[i]导致return后)，横向遍历才会往右挪动；回溯第n个can[i] 回溯第n-1个can[i];
剪枝
一次回溯只能对消一层递归；每次return只是从曾经增加进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) {
// 找到了数字和为 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
剖析
在原有根底上设限每个数字在每个组合中只能应用 一次 且不蕴含反复的组合
Arrays升序；纵向遍历时就要i++；Set去重
Set去重超时了！！！ 要在增加汇合的时候就判断是否反复，取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) {
// 找到了数字和为 target 的组合
if (sum == target) {
res.add(new LinkedList<>(path));
return;
}
for (int i = idx; i < candidates.length && sum + candidates[i] <= target; i++) {
// 要对横向遍历时应用过的元素进行跳过 因为一样的元素在深度递归时曾经把蕴含此元素的所有可能后果全副枚举过了
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>
找到所有的子串组合，判断子串是否是回文串，依据索引切割 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;
}
//起始地位后移，保障不反复
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;
}
}总结
- 题目给定的数据集如果应用数组的形式，要判断是否有序，没有阐明有序最好视情排序
- 回溯横向挪动的机会肯定是某个纵向递归完结
- 看清题目要求，将串的所有子串都宰割成回文子串
- 横向遍历逻辑 纵向递归startIndex++逻辑 回溯逻辑
发表回复