欢迎关注个人公众号:爱喝可可牛奶
LeetCode 39. 组合总和 40.组合总和II 131.分割回文串
LeetCode 39. 组合总和
分析
回溯可看成对二叉树节点进行组合枚举,分为横向和纵向
每次往sum添加新元素时,必须明确从can哪个位置开始,定义变量pos
返回条件 sum == target 或 sum > target; 横向结束条件 没有新元素可以添加了即pos
bt(can, sum, tar, pos){
if(sum == tar) add return;
if(sum > tar) pos++ return;
for(int i = pos; i
这个回溯考虑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
代码
class Solution {
List> res = new ArrayList();
LinkedList path = new LinkedList();
public List> 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 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> res = new LinkedList();
LinkedList path = new LinkedList();
int sum = 0;
public List> 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 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.分割回文串
分析
切割子串,保证每个子串都是 回文串
找到所有的子串组合,判断子串是否是回文串,根据索引切割 startIndex endIndex if(start-end) is ; res.add
代码
class Solution {
List> res = new ArrayList();
LinkedList path = new LinkedList();
public List> 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
总结
- 题目给定的数据集如果使用数组的方式,要判断是否有序,没有说明有序最好视情排序
- 回溯横向移动的时机一定是某个纵向递归结束
- 看清题目要求,将串的所有子串都分割成回文子串
- 横向遍历逻辑 纵向递归startIndex++逻辑 回溯逻辑
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net