39. 组合总和
题目链接:39. 组合总和
文档讲解:代码随想录
状态:卡了一会儿
思路:先排序,方便剪枝。允许数字重复使用,因此递归调用时传入当前索引i。
题解:
public class Solution {// 用于存储所有可能的组合private List<List<Integer>> res = new ArrayList<>();// 当前正在构建的组合private LinkedList<Integer> list = new LinkedList<>();// 用于存储当前组合的和private int sum = 0;/*** 组合求和函数* @param candidates 候选数字数组* @param target 目标数字* @return 所有可能的组合列表*/public List<List<Integer>> combinationSum(int[] candidates, int target) {// 首先对候选数字进行排序Arrays.sort(candidates);// 调用回溯函数backtracking(candidates, target, 0);// 返回所有可能的组合return res;}/*** 回溯函数,用于递归地搜索所有可能的组合* @param candidates 候选数字数组* @param target 目标数字* @param startIndex 当前搜索的起始索引*/public void backtracking(int[] candidates, int target, int startIndex) {// 如果当前和大于目标,则回溯if (sum > target) {return;}// 如果当前和等于目标,将当前组合添加到结果列表中if (sum == target) {res.add(new ArrayList<>(list));return;}// 遍历候选数字,从startIndex开始,直到sum+当前数字大于目标或遍历完所有数字for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {// 将当前数字添加到当前组合中,并更新当前和sum += candidates[i];list.add(candidates[i]);// 递归调用回溯函数,搜索当前数字之后的组合backtracking(candidates, target, i); // 注意这里传入i,允许重复使用同一个数字// 回溯,移除当前数字,恢复当前和sum -= candidates[i];list.removeLast();}}
}
40.组合总和II
题目链接:40.组合总和II
文档讲解:代码随想录
状态:自己在去重的时候,将集合中的重复元素也去掉了,导致结果缺少。集合(数组candidates)有重复元素,但还不能有重复的组合,这个不会处理。
思路:使用used数组标记树层或树枝中的元素是否使用,从而将集合有重复元素和结果又重复组合区分开。
默认used数组都为false,树层有重复元素和树枝有重复元素的关键区别在于used[i-1]是否为true,树层中元素因为回溯会使used[i-1]恢复成false,树枝中有重复元素则used[i-1]使用过,因此为true。
题解:
List<List<Integer>> res = new ArrayList<>(); // 结果集LinkedList<Integer> list = new LinkedList<>(); // 当前组合int sum = 0; // 当前组合的和public List<List<Integer>> combinationSum2(int[] candidates, int target) {Arrays.sort(candidates); // 排序,方便后续处理boolean[] used = new boolean[candidates.length]; // 记录每个元素是否被使用过Arrays.fill(used, false); // 初始化为未使用backtracking(candidates, used, target, 0); // 开始回溯return res; // 返回结果集}public void backtracking(int[] candidates, boolean[] used, int target, int startIndex) {if (sum == target) { // 当前组合的和等于目标值res.add(new ArrayList<>(list)); // 将当前组合加入结果集return;}for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {if (i > 0 && candidates[i] == candidates[i - 1] && !used[i - 1]) { // 去重continue;}sum += candidates[i]; // 做出选择,更新当前组合的和list.add(candidates[i]); // 将当前元素加入当前组合used[i] = true; // 标记当前元素已被使用backtracking(candidates, used, target, i + 1); // 递归,处理下一个元素list.removeLast(); // 撤销选择,回溯到上一个状态used[i] = false; // 标记当前元素未被使用sum -= candidates[i]; // 更新当前组合的和}}
131.分割回文串
题目链接:131.分割回文串
文档讲解:代码随想录
状态:不会,想到分割方法,代码没写出来!
代码没写出来的原因:
- 写成了
if (startIndex == chars.length) { res.add(new ArrayList<>(list)); return; }
认为 startIndex == chars.length - 1 时将list添加到res中。实际上因为backtracking(chars, i + 1);
的存在,res中添加list的操作都是在下次递归中完成的,而这时i+1就导致startIndex每次都比原来的大了1。 - 写成了
new String(chars, startIndex, i)
,而实际上第三个参数是长度
// 存储所有分割方案的列表List<List<String>> res = new ArrayList<>();// 当前正在构建的分割方案LinkedList<String> list = new LinkedList<>();/*** 将字符串分割成回文子串的方案* @param s 输入的字符串* @return 分割方案的列表*/public List<List<String>> partition(String s) {// 将字符串转换为字符数组char[] chars = s.toCharArray();// 从索引0开始回溯backtracking(chars, 0);// 返回所有分割方案return res;}/*** 回溯函数,用于递归地搜索所有可能的回文子串分割方案* @param chars 字符串转换后的字符数组* @param startIndex 当前搜索的起始索引*/public void backtracking(char[] chars, int startIndex) {// 如果当前索引等于字符数组的长度,说明已经处理完所有字符,将当前方案添加到结果中if (startIndex == chars.length) {res.add(new ArrayList<>(list));return;}// 从当前索引开始,尝试所有可能的分割点for (int i = startIndex; i < chars.length; i++) {// 如果从startIndex到i的子串是回文串,则将其添加到当前方案中if (isPalindrome(chars, startIndex, i)) {// 添加子串到当前方案list.add(new String(chars, startIndex, i - startIndex + 1));// 递归调用回溯函数,继续搜索i之后的分割方案backtracking(chars, i + 1);// 回溯,移除最后一个添加的子串,以便尝试其他分割方案list.removeLast();}}}/*** 判断子串是否为回文串* @param chars 字符数组* @param start 子串的起始索引* @param end 子串的结束索引* @return 如果子串是回文串返回true,否则返回false*/public boolean isPalindrome(char[] chars, int start, int end) {// 从子串的两端向中间遍历,如果字符不相等则不是回文串while (start <= end) {if (chars[start] != chars[end]) {return false;}start++;end--;}// 如果遍历完所有字符都相等,则子串是回文串return true;}