day20 | 39. 组合总和 40.组合总和ii 131.分割回文串-爱代码爱编程
语言
Java
39. 组合总和
题目
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
思路
本题依然采取递归的方法，我先定义了两个全局变量 一个结果二维数组，一个收集数据的一维数组。在主方法里对数组进行排序，然后进行递归，最后返回结果数组。
递归三部曲 递归参数：target、数组candidates、sum、index
递归终止条件：sum等于target 将合格的数组加入到结果数组中
单层递归：for循环控制结果集大小和遍历次数、递归用来收集数据。
代码
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates, 0, target, 0);
return res;
}
public void backtracking(int[] candidates, int sum, int target, int index) {
if (sum == target) {
res.add(new ArrayList<>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
if (sum + candidates[i] > target) return;
sum += candidates[i];
list.add(candidates[i]);
backtracking(candidates, sum, target, i);
sum -= candidates[i];
list.removeLast();
}
}
}易错点
需要进行剪枝操作，第一步就是数组要排序，第二部在单层递归的时候进行判断,如果sum > target就直接返回。
40.组合总和II
题目
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
思路
本题依然采取递归的方法，我先定义了两个全局变量 一个结果二维数组，一个收集数据的一维数组。在主方法里对数组进行排序，然后进行递归，最后返回结果数组。
递归三部曲 递归参数：target、数组candidates、sum、index
递归终止条件：sum等于target 将合格的数组加入到结果数组中
单层递归：for循环控制结果集大小和遍历次数、递归用来收集数据。并且递归的index参数变为i+1
需要注意的是本题需要去重，不仅要将list结果去重，并且每个元素只能使用一次。
代码
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> list = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates, target, 0, 0);
return res;
}
public void backtracking(int[] candidates, int target, int sum, int index) {
if (sum == target) {
res.add(new ArrayList<>(list));
return;
}
for (int i = index; i < candidates.length; i++) {
if (sum + candidates[i] > target) return;
if (i > index && candidates[i] == candidates[i - 1]) continue;
list.add(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i + 1);
sum -= candidates[i];
list.removeLast();
}
}
}易错点
需要对list进行去重
如果没有去重重复的list数组
131.分割回文串
题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
。返回 s 所有可能的分割方案。
思路
本题依然采取递归的方法，我先定义了两个全局变量 一个结果二维数组，一个收集字符串的一维数组。在主方法里进行递归，最后返回结果数组。下面递归三部曲。
递归终止条件：分割线大于等于字符串长度，代表切完且判断完了，将字符串数组加到结果数组中。
递归参数：字符串，索引。索引也就代表分割线
单程递归逻辑：判断是否为回文数，如果是就加到字符串数组，不是就继续切割。记得回溯
代码
class Solution {
List<List<String>> res = new ArrayList<>();
List<String> list = new LinkedList<>();
public List<List<String>> partition(String s) {
backTracking(s, 0);
return res;
}
public void backTracking(String s, int startIndex) {
if (startIndex >= s.length()) {
res.add(new ArrayList<>(list));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPartition(s, startIndex, i)) {
String str = s.substring(startIndex, i + 1);
list.add(str);
} else {
continue;
}
backTracking(s, i + 1);
list.removeLast();
}
}
public boolean isPartition(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;
}
}易错点
终止条件为什么是大于字符串长度一开始我没理解，因为他是代表分割线，而且先进行判断的是不是回文数。
还有这道题用List和Deque都可以。
总结
回溯算法的第二天 接触到了切割。明天继续努力！
博观而约取、厚积而薄发。