Efficiently finding a path in a matrix whose elements sum to a target number?

Question

Programming Problem

Input: m x n matrix of strictly positive numbers, target number T.

Output: a simple path starting at entry (0,0) and ending on the bottom row. We are only allowed to move right or down at any given step. Furthermore, the path elements MUST sum up to exactly T. There are no additional constraints.

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)?

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: Finding a path whose elements sum up to a given number in a matrix

Answer 1

If you can move only down or right as you said here Efficiently finding a path in a matrix whose elements sum to a target number?, there is a solution which works in O(nmT):

// let a be given matrix
// d is 3-dimensional matrix: d[X-position][Y-position][sum]
vector<vector<vector<bool>>> d(n, vector<vector<bool>(m, vector<bool>(T + 1, false)));

// initialize dynamics
if (a[0][0] < T) {
    d[0][0][a[0][0]] = true;
}

// calcualte dynamics
for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++) {
        if (i == 0 && j == 0) {  // already calculated
            continue;
        }
        for (int k = 0; k <= T; k++) {
            bool isPossible = false;
            int prevSum = k - a[i][j];
            if (i > 0 && prevSum >= 0)
                isPossible |= d[i - 1][j][prevSum];  // step down
            if (j > 0 && prevSum >= 0)
                isPossible |= d[i][j - 1][prevSum];  // step right
            d[i][j][k] = isPossible;
    }

If one of the d[n][i][T] for each i is true (iterating over bottom row), then path exists, otherwise not.

Restoring path is not so hard too, just go up if d[i - 1][j][sum - a[i][j]] is true (or i is 0), otherwise left.

UPD. This approach won't work with negative numbers.

UPD2. It would be great if someone tells how to initialize n-dimensional vectors with known size not such weird.