Untitled

public class PathSumII {
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        List<Integer> currentPath = new ArrayList<>();
        findPaths(root, targetSum, currentPath, result);
        return result;
    }

    private void findPaths(TreeNode node, int targetSum, List<Integer> currentPath, List<List<Integer>> result) {
        if (node == null) return;

        // Add the current node to the path
        currentPath.add(node.val);

        // Check if it's a leaf and the path sum equals targetSum
        if (node.left == null && node.right == null && targetSum - node.val == 0) {
            result.add(new ArrayList<>(currentPath)); // Add a copy of the path
        } else {
            // Recurse on the left and right subtrees
            findPaths(node.left, targetSum - node.val, currentPath, result);
            findPaths(node.right, targetSum - node.val, currentPath, result);
        }

        // Backtrack: remove the last node added
        currentPath.remove(currentPath.size() - 1);
    }
}