Algorithm design: find any path in an undirected acyclic graph which has a total sum of the nodes as a specific value


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.