文章目录
- day23:回溯part3,继续组合问题
- 39.组合总和
- 40.组合总和 II
- 131.分割回文串
day23:回溯part3,继续组合问题
39.组合总和
class Solution {
List<List<Integer>> ans = new ArrayList<>();
List<Integer> path = new LinkedList<>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backtracking(candidates, target, 0, 0);
return ans;
}
public void backtracking(int[] candidates, int target, int sum, int startIndex) {
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum > target) break;
path.add(candidates[i]);
sum += candidates[i];
backtracking(candidates, target, sum, i);
path.removeLast();
sum -= candidates[i];
}
}
}
40.组合总和 II
class Solution {
List<List<Integer>> ans = 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, 0, 0);
return ans;
}
public void backtracking(int[] candidates, int target, int sum, int startIndex) {
if (sum == target) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < candidates.length; i++) {
if (sum > target) break;
if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) continue;
path.add(candidates[i]);
sum += candidates[i];
used[i] = true;
backtracking(candidates, target, sum, i + 1);
path.removeLast();
sum -= candidates[i];
used[i] = false;
}
}
}
131.分割回文串
class Solution {
List<List<String>> ans = new ArrayList<>();
List<String> path = new LinkedList<>();
public List<List<String>> partition(String s) {
backtracking(s, 0);
return ans;
}
private void backtracking(String s, int startIndex) {
if (startIndex >= s.length()) {
ans.add(new ArrayList<>(path));
return;
}
for (int i = startIndex; i < s.length(); i++) {
if (isPalindrome(s, startIndex, i))
path.add(s.substring(startIndex, i + 1));
else continue;
backtracking(s, i + 1);
path.removeLast();
}
}
private boolean isPalindrome(String s, int start, int end) {
for (int i = start, j = end; i < j; i++, j--) {
if (s.charAt(i) != s.charAt(j))
return false;
}
return true;
}
}