# 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`.