算法训练营（day27）
回溯算法模板
1
2
3
4
5
6
7
8
9
10
11
12
| void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表);
回溯，撤销处理结果
}
}
|
39. 组合总和
题目链接：https://leetcode.cn/problems/combination-sum/description/
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
解题思路
解题过程：回溯
- 定义终止条件：当 累加值 等于目标值时，返回数组集合
- 定义循环条件
- 横向：从
startIndex 遍历到 candidates.length
- 纵向： 无限制重复被选取，因此累加
candidates 的值 不需要使 i 自动加一
- 回溯：
sum 不需要回滚
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backTrack(candidates, target, 0, 0);
return result;
}
public void backTrack(int[] candidates, int target, int startIndex, int sum){
if(candidates == null){
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]);
backTrack(candidates, target, i, sum + candidates[i]);
path.removeLast();
}
}
}
|
40. 组合总和 II
题目链接：https://leetcode.cn/problems/combination-sum-ii/description/
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
解题思路
解题过程：回溯
- 定义终止条件：当 累加值 等于目标值时，返回数组集合
- 定义循环条件
- 横向：从
startIndex 遍历到 candidates.length，由于每个数字在每个组合中只能使用 一次 ，因此要添加 去重 判断
- 纵向： **每个数字在每个组合中只能使用一次 **，因此累加
candidates 的值 需要使 i 自动加一
- 回溯：
sum 需要回滚
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
List<List<Integer>> result = new ArrayList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
backTrack(candidates, target, 0, 0);
return result;
}
public void backTrack(int[] candidates, int target, int startIndex, int sum){
if(sum == target){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++){
if(i > startIndex && candidates[i] == candidates[i - 1]){
continue;
}
path.add(candidates[i]);
sum += candidates[i];
backTrack(candidates, target, i + 1, sum);
int tmp = path.getLast();
sum -= tmp;
path.removeLast();
}
}
}
|
131. 分割回文串
题目链接：https://leetcode.cn/problems/palindrome-partitioning/description/
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
解题思路
解题过程：回溯
- 定义终止条件：当
startIndex 大于等于 字符串s 的长度大小时，说明 回文串分割完成
- 定义 回文 判断：双指针 判断首尾字符是否相等
- 定义循环条件
- 横向：从
startIndex 遍历到 s.length()
- 纵向：当满足 回文 判断，将字符串
[startIndex, i + 1)截取成 子字符串 存储在 path 中
- 回溯：从
i + 1 继续执行 backTrack
详细代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
List<List<String>> result = new ArrayList<>();
LinkedList<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backTrack(s, 0);
return result;
}
public boolean isPalidrome(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;
}
public void backTrack(String s, int startIndex){
if(startIndex >= s.length()){
result.add(new ArrayList<>(path));
return;
}
for(int i = startIndex; i < s.length(); i++){
if(isPalidrome(s, startIndex, i)){
String str = s.substring(startIndex, i + 1);
path.add(str);
}else{
continue;
}
backTrack(s, i + 1);
path.removeLast();
}
}
}
|
