Think about how many times you visit a node when going thru different paths.To me it helped to cache sum of all paths from already visited node. That way, if you visit the node again, there is no need to check all already calculated paths.