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?