The question was asked in an interview, and I’m not sure if this is the most optimized answer, but here goes-
You have an undirected acyclic graph, where each node has a non-negative value
x and the edges have 0 value. You need to find a path with any number of nodes on it such that the total sum of all node values is exactly
k. There are
N nodes in the graph. You can start at any node.
I gave the brute-force solution for this problem, which is basically do a dis on each node until you find a valid “root” node, such that it has a path to one of the other nodes, with a total sum being
k. The time complexity of this solution would be
n^2, since we are doing DFS on each node.
The question was posed as a delivery problem, where you have
N connected houses, each having a package of weight
k, and the truck can start at any house and should follow a path, and has to pick the package from every house that is on that path. The weights should sum exactly to