第七章 回溯算法part02
39. 组合总和
- 本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
思路
树形结构：
cr：代码随想录
- 取2的时候，剩余集合是{2，5，3}，因为元素可以重复使用。
伪代码
//变量依然是result和path
private List<List<Integer>> result = new ArrayList<>();
private List<Integer> path = new ArrayList<>();
private void backtracking(int[] candidates, int target, int sum, int startIndex){
//终止条件
if(sum > target) return;
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
//for循环实际上就是遍历节点子孩子的过程
//如何剪枝？一般是在for循环中。如果对数组进行排序后，candidates[i]+sum>target，后面都不用算了
// for(i = startIndex; i < candidates.length; i++){
for(i = startIndex; i < candidates.length&&candidates[i]+sum <= target; i++){
path.add(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i); //选2后剩余集合253，所以还是可以从i开始
sum -= candidates[i];
path.remove(path.length - 1);
}
}
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] candidates, int target, int sum, int startIndex){
if(sum > target) return;
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i < candidates.length; i++){
if (sum + candidates[i] > target) break;
path.add(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i); //这里参数是i不是startIndex
sum -= candidates[i];
path.remove(path.size()-1); //注意这里是size()
}
}
public List<List<Integer>> combinationSum(int[] candidates, int target) {
path.clear();
result.clear();
Arrays.sort(candidates);
backtracking(candidates, target, 0, 0); //这里注意后面两个参数
return result;
}
}
这样剪枝也可以
for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++)
40.组合总和II
- 本题开始涉及到一个问题了：去重。
- 注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。
思路
- 在搜索的过程中进行去重：使用过的元素就不再使用了
- 一定要排序，让相邻的元素放在一起。
- used数组，使用过的就是下标1，没使用过的就是0。有树层和树枝去重，树枝中有同时出现多个1，但是树层上再取相同的数，搜出的组合一定是重复的。所以重点是树层去重
-
当 used[i - 1] == false 时，表示在当前层级中，前一个相同的元素已经被使用且已经被回溯（即从路径中移除），因此在同一树层中再次遇到相同的元素应当跳过，以避免重复的组合。
cr：代码随想录
伪代码
//全局变量依然是path和result
private void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used) {
if(sum > target) return;
if(sum == target) {
result.add(new ArrayList<>(path));
return;
}
for(i=startIndex; i<candidates.length&&candidates[i]+sum<=target; i++){
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
if(i>0&&candidates[i] == candidates[i-1]&& used[i-1]==false){
continue;
}
sum += candidates[i];
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1，这里是i+1，每个数字在每个组合中只能使用一次
used[i] = false;
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
class Solution {
private List<Integer> path = new ArrayList<>();
private List<List<Integer>> result = new ArrayList<>();
private void backtracking(int[] candidates, int target, int sum, int startIndex, boolean[] used)
{
if(sum > target) return;
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++){
if(i>0 && candidates[i] == candidates[i-1] && used[i-1] == false) continue; //注意这里是used[i-1] == false
sum += candidates[i];
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, target, sum, i+1, used);
used[i] = false;
path.remove(path.size()-1);
sum -= candidates[i];
}
}
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
boolean[] used = new boolean[candidates.length];
Arrays.fill(used, false);//注意这个方法
path.clear();
result.clear();
Arrays.sort(candidates);
backtracking(candidates, target, 0, 0, used);
return result;
}
}
131.分割回文串
- 本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。
思路
- 字符串的分割也可以转换为树形结构
cr：代码随想录
伪代码
//全局变量 还是path和result
List<List<String>> result = new ArrayList<>();
Deque<String> path = new LinkedList<>();
private void backTracking(String s, int startIndex) {
//终止条件 startIndex就是切割的线
if(startIndex >= s.length()){
lists.add(new ArrayList(deque));
return;
}
for(int i = startIndex; i<s.length(); i++){
//判断切割的字串是不是回文，是就加入
//每一层递归里处理的逻辑就是startIndex和i形成的左闭右闭的区间,for循环中i是不断++的，startIndex是相对固定的
if(isPalindrome(s, startIndex, i)){
String str = s.substring(startIndex, i - startIndex + 1);
path.addLast(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;
}
class Solution {
List<List<String>> result = new ArrayList<>();
Deque<String> path = new LinkedList<>();
private void backtracking(String s, int startIndex){
if(startIndex >= s.length()){
result.add(new LinkedList<>(path));
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isPalindrome(s, startIndex, i)){
String str = s.substring(startIndex, i+1);
path.addLast(str);
}else{
continue;
}
backtracking(s, i+1);
path.removeLast();
}
}
private boolean isPalindrome(String s, int startIndex, int end){
while(startIndex < end){
if(s.charAt(startIndex) != s.charAt(end)) return false;
startIndex++;
end--;
}
return true;
}
public List<List<String>> partition(String s) {
backtracking(s, 0);
return result;
}
}
出现的问题：
String str = s.substring(startIndex, i - startIndex + 1); 会导致运行时错误，因为 substring 方法的第二个参数是结束索引（非包含），而你的计算方式会导致索引越界或不正确。正确的方式应该是直接使用 i + 1 作为结束索引，因为 substring 方法的第二个参数是结束索引，而不是长度。
此外，private boolean isPalindrome 在for循环中需要return false，只有全部循环结束后才能return true
然后可以考虑Deque，可以快速插入删除两端的元素。
