leetcode 39. 组合总和
题目描述
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
题目链接
https://leetcode.cn/problems/combination-sum/
解题思路
回溯遍历，为了方便书写终止条件。先对数组进行排序。那么如果当前和大于 target，后续的也可以不用再计算。然后用 startIndex记录当前回溯的起始下标，由于可重复，所以还是回溯当前下标，不过 target进行了修改。
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
traceBack(candidates, target, 0);
return res;
}
public void traceBack(int[] candidates, int target, int startIndex) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (target - candidates[i] < 0) break;
path.add(candidates[i]);
traceBack(candidates, target - candidates[i], i);
path.removeLast();
}
}
}
leetcode 40. 组合总和 II
题目描述
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
**注意：**解集不能包含重复的组合。
示例
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]
题目链接
https://leetcode.cn/problems/combination-sum-ii/
解题思路
关键点：
- 数组排序
target - candidates[i] < 0)时退出循环if (i > startIndex && candidates[i] == candidates[i - 1]) continue;去重，因为是有序数组，那么当前要选取的和上次已选取的一样，那么会重复出现。traceBack(candidates, target - candidates[i], i + 1);，和 39 题不同，题中要求同一个数不能重复使用两次，所以下一次得从下一个下标开始
class Solution {
List<List<Integer>> res = new ArrayList<>();
List<Integer> path = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
traceBack(candidates, target, 0);
return res;
}
public void traceBack(int[] candidates, int target, int startIndex) {
if (target == 0) {
res.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (target - candidates[i] < 0) break;
if (i > startIndex && candidates[i] == candidates[i - 1]) continue;
path.add(candidates[i]);
traceBack(candidates, target - candidates[i], i + 1);
path.removeLast();
}
}
}
leetcode 131. 分割回文串
题目描述
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
示例
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]
题目链接
https://leetcode.cn/problems/palindrome-partitioning
解题思路
关键点
- 判断字符串是否是回文串，这里用双指针法
- 如果是回文串，则添加到路径，并开始回溯
class Solution {
public List<List<String>> res = new ArrayList<>();
public List<String> path = new ArrayList<>();
public List<List<String>> partition(String s) {
traceBack(s, 0);
return res;
}
public void traceBack(String s, int start) {
if (start == s.length()) {
res.add(new ArrayList<>(path));
return;
}
for (int i = start; i < s.length(); i++) {
if (isPalindrome(s, start, i)) {
path.add(s.substring(start, i + 1));
traceBack(s, i + 1);
path.removeLast();
}
}
}
public boolean isPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left++) != s.charAt(right--)) return false;
}
return true;
}
}
评论