Path sum in a Directed Acyclic Graph

Given a directed acyclic graph, determine if any branch returns a path sum that equals 22. In the example below, such a path can be found at (7 + 8 + 3 + 4). What is the run time complexity of such an algorithm?

``````      7
/ \
8   6
/ \ / \
2   3   8
/   /    \
5   4      1
``````

This is what I came up with.

``````public boolean hasPathToSum(Node root, int sum)
{
if (root == null) return false;
if (root.value == sum && (root.left == null && root.right == null))
return true;

return hasPathToSum(root.left, sum - root.value) || hasPathToSum(root.right, sum - root.value);
}
``````

Any better suggestions on improving the complexity?

Memoization is a technique not to compute the same value twice. Note that `hasPathToSum(root, sum)` is a pure function: its result depends only on arguments, it has no side effects. It means that we can save the result of this function into some map `(root, sum) -> bool` (probably a HashMap or a TreeMap in Java, I cannot say precisely as I'm not familiar with the language).
The last optimization works only with nonnegative values. Note that the result of `hasPathToSum(v, x)` is false if x < 0. So you can make a cutoff: just return false immediately if this is the case. This optimization ensures that, for each node, `hasPathToSum` will be called with at most 23 different sum values, yielding the aforementioned running time.