路徑總和
import java.util.ArrayList;
import java.util.List;// 定義二叉樹節點類
class TreeNode {int val;TreeNode left;TreeNode right;// 構造函數，用于初始化節點值TreeNode(int x) {val = x;}
}public class PathSumProblems {// 路徑總和 I：判斷是否存在從根節點到葉子節點的路徑，使得路徑上所有節點值的和等于給定的目標值public boolean hasPathSumI(TreeNode root, int sum) {// 若根節點為空，不存在滿足條件的路徑if (root == null) {return false;}// 若當前節點為葉子節點，判斷當前節點值是否等于剩余的和if (root.left == null && root.right == null) {return root.val == sum;}// 遞歸在左子樹和右子樹中查找return hasPathSumI(root.left, sum - root.val) || hasPathSumI(root.right, sum - root.val);}// 路徑總和 II：找出所有從根節點到葉子節點的路徑，使得路徑上所有節點值的和等于給定的目標值public List<List<Integer>> pathSumII(TreeNode root, int sum) {List<List<Integer>> result = new ArrayList<>();if (root == null) {return result;}dfsII(root, sum, new ArrayList<>(), result);return result;}// 深度優先搜索輔助方法，用于路徑總和 IIprivate void dfsII(TreeNode node, int remainingSum, List<Integer> currentPath, List<List<Integer>> result) {if (node == null) {return;}// 將當前節點加入路徑currentPath.add(node.val);remainingSum -= node.val;// 若當前節點為葉子節點且剩余和為 0，說明找到了一條滿足條件的路徑if (node.left == null && node.right == null && remainingSum == 0) {result.add(new ArrayList<>(currentPath));}// 遞歸遍歷左子樹和右子樹dfsII(node.left, remainingSum, currentPath, result);dfsII(node.right, remainingSum, currentPath, result);// 回溯，移除當前節點currentPath.remove(currentPath.size() - 1);}// 路徑總和 III：計算二叉樹中路徑和等于給定值的路徑總數，路徑不需要從根節點開始，也不需要在葉子節點結束public int pathSumIII(TreeNode root, int sum) {if (root == null) {return 0;}// 以當前節點為起點的路徑數量int pathsFromRoot = countPathsIII(root, sum);// 左子樹中的路徑數量int pathsInLeft = pathSumIII(root.left, sum);// 右子樹中的路徑數量int pathsInRight = pathSumIII(root.right, sum);return pathsFromRoot + pathsInLeft + pathsInRight;}// 輔助方法，用于計算以當前節點為起點的路徑數量private int countPathsIII(TreeNode node, int remainingSum) {if (node == null) {return 0;}int paths = 0;// 若當前節點值等于剩余和，說明找到了一條路徑if (node.val == remainingSum) {paths++;}// 遞歸在左子樹和右子樹中查找paths += countPathsIII(node.left, remainingSum - node.val);paths += countPathsIII(node.right, remainingSum - node.val);return paths;}public static void main(String[] args) {// 構建一個簡單的二叉樹TreeNode root = new TreeNode(10);root.left = new TreeNode(5);root.right = new TreeNode(-3);root.left.left = new TreeNode(3);root.left.right = new TreeNode(2);root.right.right = new TreeNode(11);root.left.left.left = new TreeNode(3);root.left.left.right = new TreeNode(-2);root.left.right.right = new TreeNode(1);PathSumProblems solution = new PathSumProblems();// 測試路徑總和 Iint targetSumI = 8;boolean resultI = solution.hasPathSumI(root, targetSumI);System.out.println("路徑總和 I：是否存在路徑和為 " + targetSumI + " 的路徑: " + resultI);// 測試路徑總和 IIint targetSumII = 8;List<List<Integer>> resultII = solution.pathSumII(root, targetSumII);System.out.println("路徑總和 II：路徑和為 " + targetSumII + " 的所有路徑: " + resultII);// 測試路徑總和 IIIint targetSumIII = 8;int resultIII = solution.pathSumIII(root, targetSumIII);System.out.println("路徑總和 III：路徑和為 " + targetSumIII + " 的路徑總數: " + resultIII);}
}
組合總和
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class CombinationSumProblems {// 組合總和 I：找出 candidates 中所有可以使數字和為 target 的組合，candidates 中的數字可以無限制重復被選取public List<List<Integer>> combinationSumI(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();if (candidates == null || candidates.length == 0) {return result;}// 調用回溯方法backtrackI(candidates, target, 0, new ArrayList<>(), result);return result;}private void backtrackI(int[] candidates, int remaining, int start, List<Integer> current, List<List<Integer>> result) {// 如果剩余值為 0，說明找到了一個有效的組合if (remaining == 0) {result.add(new ArrayList<>(current));return;}// 如果剩余值小于 0，說明當前組合不滿足條件if (remaining < 0) {return;}// 從 start 開始遍歷 candidates 數組for (int i = start; i < candidates.length; i++) {// 將當前數字加入組合current.add(candidates[i]);// 遞歸調用，由于數字可以重復使用，下一次遞歸的 start 仍然是 ibacktrackI(candidates, remaining - candidates[i], i, current, result);// 回溯，移除最后一個數字current.remove(current.size() - 1);}}// 組合總和 II：找出 candidates 中所有可以使數字和為 target 的組合，candidates 中的每個數字在每個組合中只能使用一次public List<List<Integer>> combinationSumII(int[] candidates, int target) {List<List<Integer>> result = new ArrayList<>();if (candidates == null || candidates.length == 0) {return result;}// 對數組進行排序，方便去重Arrays.sort(candidates);// 調用回溯方法backtrackII(candidates, target, 0, new ArrayList<>(), result);return result;}private void backtrackII(int[] candidates, int remaining, int start, List<Integer> current, List<List<Integer>> result) {// 如果剩余值為 0，說明找到了一個有效的組合if (remaining == 0) {result.add(new ArrayList<>(current));return;}// 如果剩余值小于 0，說明當前組合不滿足條件if (remaining < 0) {return;}// 從 start 開始遍歷 candidates 數組for (int i = start; i < candidates.length; i++) {// 跳過重復的數字，避免結果中出現重復組合if (i > start && candidates[i] == candidates[i - 1]) {continue;}// 將當前數字加入組合current.add(candidates[i]);// 遞歸調用，下一次遞歸的 start 為 i + 1，因為每個數字只能使用一次backtrackII(candidates, remaining - candidates[i], i + 1, current, result);// 回溯，移除最后一個數字current.remove(current.size() - 1);}}// 組合總和 III：找出所有相加之和為 n 的 k 個數的組合，組合中只允許含有 1 - 9 的正整數，并且每種組合中不存在重復的數字public List<List<Integer>> combinationSumIII(int k, int n) {List<List<Integer>> result = new ArrayList<>();// 調用回溯方法backtrackIII(k, n, 1, new ArrayList<>(), result);return result;}private void backtrackIII(int k, int remaining, int start, List<Integer> current, List<List<Integer>> result) {// 如果當前組合的長度等于 k 且剩余值為 0，說明找到了一個有效的組合if (current.size() == k && remaining == 0) {result.add(new ArrayList<>(current));return;}// 如果當前組合的長度大于 k 或者剩余值小于 0，說明當前組合不滿足條件if (current.size() > k || remaining < 0) {return;}// 從 start 開始遍歷 1 - 9 的數字for (int i = start; i <= 9; i++) {// 將當前數字加入組合current.add(i);// 遞歸調用，下一次遞歸的 start 為 i + 1，避免重復使用數字backtrackIII(k, remaining - i, i + 1, current, result);// 回溯，移除最后一個數字current.remove(current.size() - 1);}}public static void main(String[] args) {CombinationSumProblems solution = new CombinationSumProblems();// 測試組合總和 Iint[] candidatesI = {2, 3, 6, 7};int targetI = 7;List<List<Integer>> resultI = solution.combinationSumI(candidatesI, targetI);System.out.println("組合總和 I：和為 " + targetI + " 的所有組合: " + resultI);// 測試組合總和 IIint[] candidatesII = {10, 1, 2, 7, 6, 1, 5};int targetII = 8;List<List<Integer>> resultII = solution.combinationSumII(candidatesII, targetII);System.out.println("組合總和 II：和為 " + targetII + " 的所有組合: " + resultII);// 測試組合總和 IIIint k = 3;int n = 9;List<List<Integer>> resultIII = solution.combinationSumIII(k, n);System.out.println("組合總和 III：和為 " + n + " 的 " + k + " 個數的所有組合: " + resultIII);}
}
