title: Efficiently finding a path in a matrix whose elements sum to a target number?
body: <p><strong>Programming Problem</strong></p>
  
  <p><em>Input:</em> m x n matrix of strictly positive numbers, target number T.</p>
  
  <p><em>Output:</em> a simple path starting at entry (0,0) and ending on the bottom row. We are only allowed to <em>move right or down</em> at any given step. Furthermore, the path elements MUST sum up to exactly T. There are no additional constraints.</p>
  
  <p>I have implemented a correct brute-force solution, but we're talking about exponential time. Does a more efficient solution exist (perhaps using dynamic programming)?</p>
  
  <p>I saw a similar existing question, but the answers are limited and someone claimed this problem to be NP-Complete, but I have been unable to verify this:
  <a href="https://stackoverflow.com/questions/50653255/finding-a-path-whose-elements-sum-up-to-a-given-number-in-a-matrix">Finding a path whose elements sum up to a given number in a matrix</a></p>