# Recursion solution, I don't know what algorithm it is ....

• There're 2 cases for each node:

1. must have the node, then it's children should also be used.
2. must not have the node, then there should be 4 cases:
mustHave(node.left, sum)
+ mustHave(node.right, sum)
+ mustNotHave(node.left, sum)
+ mustNotHave(node.right, sum);
``````/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public int pathSum(TreeNode root, int sum) {
if(root == null) {
return 0;
}
return mustHave(root, sum) + mustNotHave(root, sum);
}

public int mustHave(TreeNode node, int sum) {
if(node == null) {
return 0;
}
int result = node.val == sum ? 1 : 0;
result += mustHave(node.left, sum - node.val) + mustHave(node.right, sum - node.val);
return result;
}
public int mustNotHave(TreeNode node, int sum) {
if(node == null) {
return 0;
}
return mustHave(node.left, sum) + mustHave(node.right, sum)
+ mustNotHave(node.left, sum) + mustNotHave(node.right, sum);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.