How to solve the coin change problem where you have to find the minimum no of coins required to make a sum N(given) from infinite no of coins of denominations given in an array of size M. for example denominations available {1,2,3,5,6} and N = 11 answer is 2(5+6). But here N can be given negative value and coins can also be negative values.

One solution is construction a graph with vertices: sum of all negative coins,...,-1,0,1,2,.... sum of all positive values. and having an edge between vertex i and j if (i-j) is one of the coins available. Then finding the shortest path using bfs on node number 0.

If M = 1e5 and each coin -1e5 < Ai < 1e5 this solution will fail. How to solve this for larger constraints?