代码随想录算法训练营day27 | 题目39、题目40、题目131
题目一描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
提示：
1 <= candidates.length <= 30
2 <= candidates[i] <= 40
candidates 的所有元素 互不相同
1 <= target <= 40
解题思路
在求和问题中，排序之后加剪枝是常见的套路。
如果解集不能包含重复的组合，i就从startIndex开始，如果是不同的集合，就从0开始，类似电话号码。
如果每个元素可以用无限次，循环里的startIndex就传递i，如果只能用一次，就传递i+1.
代码实现
方法一：
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates); // 排序方便后面剪枝
backtracking(path, res, candidates, target, 0, 0);
return res;
}
private void backtracking(List<Integer> path, List<List<Integer>> res, int[] candidates, int target,
int sum, int startIndex) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
sum += candidates[i];
if (sum > target) { // 只有在候选集合升序的时候放在回溯前合适，本层后续循环都不用进入了。
break; // 后面的元素都会大，所以直接跳出循环。break和return都一样。
}
path.add(candidates[i]);
backtracking(path, res, candidates, target, sum, i);
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
题目二描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5,
输出:
[
[1,2,2],
[5]
]
提示:
1 <= candidates.length <= 100
1 <= candidates[i] <= 50
1 <= target <= 30
解题思路
依旧是排序后剪枝，注意每一层的相同元素只能使用一次，每一个树枝的重复元素可以用多次。
也可以用辅助数组，但是要注意理解里面元素true和false的状态代表的含义。
代码实现
方法一：
class Solution {
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtracking(candidates, res, path, target, 0, 0);
return res;
}
private void backtracking(int[] candidates, List<List<Integer>> res, List<Integer> path, int target, int startIndex,
int sum) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
// 保证了每层的这个数只能用一次，因为每层第一次使用时 i = startIndex
// 这里是树层去重
if (i > startIndex && candidates[i] == candidates[i - 1]) {
continue;
}
sum += candidates[i];
if (sum > target) {
return;
}
path.add(candidates[i]);
backtracking(candidates, res, path, target, i + 1, sum); // 这里是树枝去重，去的是自己
sum -= candidates[i];
path.remove(path.size() - 1);
}
}
}
方法二：
class Solution {
boolean[] used;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
used = new boolean[candidates.length];
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
Arrays.sort(candidates);
backtracking(candidates, res, path, target, 0, 0);
return res;
}
private void backtracking(int[] candidates, List<List<Integer>> res, List<Integer> path, int target, int startIndex,
int sum) {
if (sum == target) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; 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]) {
continue;
}
sum += candidates[i];
if (sum > target) {
return;
}
path.add(candidates[i]);
used[i] = true;
backtracking(candidates, res, path, target, i + 1, sum); // 这里是树枝去重，去的是自己
sum -= candidates[i];
path.remove(path.size() - 1);
// 因为这里会再次置为false，同层下一个就知道false是使用过了，同一树枝还是true。
used[i] = false;
}
}
}
题目三描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串（回文串是向前和向后读都相同的字符串）。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a"
输出：[["a"]]
提示：
1 <= s.length <= 16
s 仅由小写英文字母组成
解题思路
也是回溯，可以每次传切割好的字符串，然后对长度进行遍历回溯。
也可以传要切割的初始位置，这样操作子串的次数比较少。
代码实现
方法一：
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> subStrings = new ArrayList<>();
backtracking(s, res, subStrings);
return res;
}
private void backtracking(String s, List<List<String>> res, List<String> subStrings) {
if (s.length() == 0) {
res.add(new ArrayList<>(subStrings));
return;
}
for (int length = 1; length <= s.length(); length++) {
String subString = s.substring(0, length);
if (check(subString)) {
subStrings.add(subString);
String rightSub = s.substring(length, s.length()); // 切完剩下的子串
backtracking(rightSub, res, subStrings);
subStrings.remove(subStrings.size() - 1);
} else {
continue; // continue就是这一个树枝都不行了，return或者break就是这一层都不行了。
}
}
}
private boolean check(String s) {
int start = 0;
int end = s.length() - 1;
while (start < end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
return true;
}
}
方法二：
class Solution {
public List<List<String>> partition(String s) {
List<List<String>> res = new ArrayList<>();
List<String> subStrings = new ArrayList<>();
backtracking(s, res, subStrings, 0);
return res;
}
private void backtracking(String s, List<List<String>> res, List<String> subStrings, int startIndex) {
if (startIndex == s.length()) {
res.add(new ArrayList<>(subStrings));
return;
}
for (int i = startIndex; i < s.length(); i++) { // 本质上也是在遍历长度，只不过隐含了划分子串的操作
if (check(s, startIndex, i)) {
String subString = s.substring(startIndex, i + 1); // 放在里面减少操作次数
subStrings.add(subString);
backtracking(s, res, subStrings, i + 1); // 传递切完剩下的子串的开始下标
subStrings.remove(subStrings.size() - 1);
} else {
continue; // continue就是进入本层的下一个树枝分叉点，return或者break就是这一层都不行了，返回上一层。
}
}
}
private boolean check(String s, int start, int end) {
while (start < end) {
if (s.charAt(start++) != s.charAt(end--)) {
return false;
}
}
return true;
}
}
