# Find exact sum in path

So the question is

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to the right.

This is a common interview question on software engineering interviews, it is easily solved by implementing a dynamic programming table in order to discern what path is the least costly.

I am now wondering, is there an easy way to solve an alternative problem? Which would be to find the exact sum of a path in an mxn grid.

For instance the input would be a 3x3 matrix and the target sum would be lets say 4. What type of technique should be used in order to find a path that equals exactly 4 to the bottom right corner from the top left corner.

• The problem is NP-hard in general (by a reduction from subset-sum) but it admits an easy psedopolynomial-time dynamic programming algorithm. – Steven Nov 24 '20 at 13:59
• Backtracking with memoization will do the job. – XRFXLP Dec 8 '20 at 9:29