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 `k`

.