第七章 回溯算法part02
39. 组合总和
本题是 集合里元素可以用无数次，那么和组合问题的差别 其实仅在于 startIndex上的控制
题目链接/文章讲解：https://programmercarl.com/0039.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8C.html
视频讲解：https://www.bilibili.com/video/BV1KT4y1M7HJ
错误：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtracking(candidates, target, 0);
return res;
}
public void backtracking(int[] candidates, int target, int index){
if(sum(path) == target){
res.add(new ArrayList(path));
return;
}
if(index == target) return;
for(int i = 0; i < candidates.length; i ++){
path.add(candidates[i]);
backtracking(candidates, target, index + 1);
path.removeLast();
}
}
public int sum(List<Integer> path){
int sum = 0;
for(int i : path){
sum += i;
}
return sum;
}
}
错误实例：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
backtracking(candidates, target, 0);
return res;
}
public void backtracking(int[] candidates, int target, int index){
if(sum(path) == target){
res.add(new ArrayList(path));
return;
}
if(sum(path) > target) return;// 更高效的剪枝
for(int i = index; i < candidates.length; i ++){
path.add(candidates[i]);
backtracking(candidates, target, i);// 不加一 有一条路是可以一直重复的
path.removeLast();
}
}
public int sum(List<Integer> path){
int sum = 0;
for(int i : path){
sum += i;
}
return sum;
}
}
40.组合总和II
本题开始涉及到一个问题了：去重。
注意题目中给我们 集合是有重复元素的，那么求出来的 组合有可能重复，但题目要求不能有重复组合。
题目链接/文章讲解：https://programmercarl.com/0040.%E7%BB%84%E5%90%88%E6%80%BB%E5%92%8CII.html
视频讲解：https://www.bilibili.com/video/BV12V4y1V73A
错误：
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.fill(used, false);
Arrays.sort(candidates);
backtracking(candidates, target, used, 0);
return res;
}
public void backtracking(int[] candidates, int target, boolean[] used, int index){
if(sum(path) == target){
res.add(new ArrayList(path));
return;
}
if(sum(path) > target) return;
for(int i = index; i < candidates.length; i ++){
if(candidates[i] == candidates[i - 1] && used[i - 1] == false && i >= 1) continue;// 报错
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, target,used, i + 1);
path.removeLast();
used[i] = false;
}
}
public int sum(List<Integer> path){
int sum = 0;
for(int i : path){
sum += i;
}
return sum;
}
}
调整顺序，另外Arrays
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new LinkedList<>();
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
Arrays.fill(used, false);
Arrays.sort(candidates);
backtracking(candidates, target, used, 0);
return res;
}
public void backtracking(int[] candidates, int target, boolean[] used, int index){
if(sum(path) == target){
res.add(new ArrayList(path));
return;
}
if(sum(path) > target) return;
for(int i = index; i < candidates.length; i ++){
if(i >= 1 && candidates[i] == candidates[i - 1] && used[i - 1] == false ) continue;
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, target,used, i + 1);
path.removeLast();
used[i] = false;
}
}
public int sum(List<Integer> path){
int sum = 0;
for(int i : path){
sum += i;
}
return sum;
}
}
131.分割回文串
本题较难，大家先看视频来理解 分割问题，明天还会有一道分割问题，先打打基础。
https://programmercarl.com/0131.%E5%88%86%E5%89%B2%E5%9B%9E%E6%96%87%E4%B8%B2.html
视频讲解：https://www.bilibili.com/video/BV1c54y1e7k6
class Solution {
List<List<String>> res = new ArrayList<>();
List<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backtracking(s, 0);
return res;
}
public void backtracking (String s, int index){
if(index == s.length()){// index 是分割线
res.add(new ArrayList(path));
return;
}
for(int i = index; i < s.length(); i ++){
String temp = s.substring(index, i + 1);//取字串
if(ishw(temp)){
path.add(temp);
backtracking(s, i + 1);
path.removeLast();
}else{
continue;
}
}
}
public boolean ishw(String s){
int i = 0, j = s.length() - 1;
while(i < j){
if(s.charAt(i) != s.charAt(j)){
return false;
}
i ++;
j --;
}
return true;
}
}
