写点什么

代码随想录 Day27 - 回溯(三)

作者:jjn0703
  • 2023-07-29
    江苏
  • 本文字数:2666 字

    阅读完需:约 9 分钟

总结

今天学习了回溯中,组合相关问题的解法。组合总和 II 中,数字需要预先排序,才能按照下标进行处理,否则结果没法做去重判定。此外,去重时,要区分“树层去重”和“树枝去重”。

39. 组合总和

package jjn.carl.backtrack;
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/24 10:14 */public class LeetCode39 { public List<List<Integer>> combinationSum(int[] candidates, int target) { Arrays.sort(candidates); List<List<Integer>> result = new ArrayList<>(); if (candidates.length == 0) { return result; } backtrack(target, result, new ArrayList<>(), 0, candidates, 0); return result; } private void backtrack(int target, List<List<Integer>> result, List<Integer> path, int sum, int[] candidates, int startIndex) { if (sum > target) { 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(target, result, path, sum + candidates[i], candidates, i); path.remove(path.size() - 1); } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int candidateNum = scanner.nextInt(); int target = scanner.nextInt(); int[] candidates = new int[candidateNum]; for (int i = 0; i < candidateNum; i++) { candidates[i] = scanner.nextInt(); } List<List<Integer>> lists = new LeetCode39().combinationSum(candidates, target); System.out.println(String.join(",", lists.toString())); }}
复制代码


40. 组合总和 II

package jjn.carl.backtrack;
import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.Scanner;
/** * @author Jiang Jining * @since 2023-07-24 23:43 */public class LeetCode40 { public List<List<Integer>> combinationSum2(int[] candidates, int target) { Arrays.sort(candidates); boolean[] used = new boolean[candidates.length]; List<List<Integer>> result = new ArrayList<>(); backtrack(candidates, target, 0, 0, result, new ArrayList<>(), used); return result; } private void backtrack(int[] candidates, int target, int sum, int startIndex, List<List<Integer>> result, List<Integer> path, boolean[] used) { if (sum > target) { return; } if (sum == target) { result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < candidates.length; i++) { if (i >= 1 && candidates[i] == candidates[i - 1] && !used[i - 1]) { continue; } path.add(candidates[i]); used[i] = true; backtrack(candidates, target, sum + candidates[i], i + 1, result, path, used); path.remove(path.size() - 1); used[i] = false; } } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int totalNum = scanner.nextInt(); int target = scanner.nextInt(); int[] candidates = new int[totalNum]; for (int i = 0; i < totalNum; i++) { candidates[i] = scanner.nextInt(); } List<List<Integer>> list = new LeetCode40().combinationSum2(candidates, target); System.out.println(String.join(",", list.toString())); }}
复制代码


131. 分割回文串

package jjn.carl.backtrack;
import java.util.ArrayList;import java.util.List;import java.util.Objects;import java.util.Scanner;
/** * @author Jjn * @since 2023/7/25 22:56 */public class LeetCode131 { public List<List<String>> partition(String s) { List<List<String>> result = new ArrayList<>(); backtrack(s, 0, new ArrayList<>(), result); return result; } private void backtrack(String s, int startIndex, List<String> path, List<List<String>> result) { if (startIndex >= s.length()) { result.add(new ArrayList<>(path)); return; } for (int i = startIndex; i < s.length(); i++) { if (!isPalindrome(s.substring(startIndex, i + 1))) { continue; } path.add(s.substring(startIndex, i + 1)); backtrack(s, i + 1, path, result); path.remove(path.size() - 1); } } private boolean isPalindrome(String s) { if (s == null || s.length() <= 1) { return true; } int left = 0, right = s.length() - 1; while (left < right) { if (!Objects.equals(s.charAt(left), s.charAt(right))) { return false; } left++; right--; } return true; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String input = scanner.nextLine(); List<List<String>> partition = new LeetCode131().partition(input); System.out.println(String.join(",", partition.toString())); }}
复制代码


发布于: 刚刚阅读数: 5
用户头像

jjn0703

关注

Java工程师/终身学习者 2018-03-26 加入

USTC硕士/健身健美爱好者/Java工程师.

评论

发布
暂无评论
代码随想录 Day27 - 回溯(三)_jjn0703_InfoQ写作社区