Grid Shortest Path

Given a NxM array, write a function what prints all possible shortest paths from element (0, 0) to (N, M), where no diagonal moves are possible. Note that to achieve this, when printing an element, next element has to be either to the right or below. No other direction produces the desired result.

Example Input:

1 2 3
4 5 6
7 8 9

Example Output:

1 2 3 6 9
1 2 5 6 9
1 2 5 8 9
1 4 5 6 9
1 4 5 8 9
1 4 7 8 9
void PrintGridShortestPath(int arr[N][M])
{
    vector<int> res;
    PrintGridShortestPathHelper(arr, res, 0, 0);
}
 
void PrintGridShortestPathHelper(int arr[N][M], vector<int> res, int Ni, int Mi)
{
    res.push_back(arr[Ni][Mi]);
 
    if (res.size() == N + M - 1)
    {
        for (int i = 0; i < N + M - 1; i++)
            cout << res[i] << " ";
        cout << endl;
        return;
    }
 
    if (Mi < M - 1)
        PrintGridShortestPathHelper(arr, res, Ni, Mi + 1);
    if (Ni < N - 1)
        PrintGridShortestPathHelper(arr, res, Ni + 1, Mi);
}