As I teach myself dynamic programming, I have learned about the coin exchange problems. Specially this site: https://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/ provides great insight about it. Specifically, the following implementation of a tabulated-DP-based solution for this problems is presented as follows:
def count(S, m, n ): # If n is 0 then there is 1 # solution (do not include any coin) if (n == 0): return 1 # If n is less than 0 then no # solution exists if (n < 0): return 0; # If there are no coins and n # is greater than 0, then no # solution exist if (m <=0 and n >= 1): return 0 # count is sum of solutions (i) # including S[m-1] (ii) excluding S[m-1] return count( S, m - 1, n ) + count( S, m, n-S[m-1] );
However, this only counts the number possibles solutions.
Question: How can I actually save these solutions for post-processing?
Previous research: In this very helpful video: https://www.youtube.com/watch?v=ENyox7kNKeY they explain how to use an array of parent pointers, to generate the actual solutions, however, I am having issues with implementing this approach with the previous tabulated solution. Any hint?