“Find minimum path sum” in a 2D grid, is a very popular question which is solved by dynamic programming. But what if instead of the minimum sum value, we return all the actual paths that lead to the minimum sum path? This was an interview question which has been puzzling me.
The original problem 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.
Input: grid = ((1,3,1) ,(1,5,1) ,(4,2,1)) output: 7 Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.
But instead of 7 I want to return (1,3,1,1,1) and all other paths that lead to sum of sum (in this case there is only one path). My current solution has exponential time complexity which is not good. Does anyone has a good solution to this problem?