[vardhanw]

In the first problem illustrated, I wanted to also get the list of coins. I made this attempt, but this hardly seems elegant. Any comments to make it better?

  n=10
  denom = [1,3,4]
  dp = [-1 for i in range(n+1)]
  dpl = [[] for i in range(n+1)]
  def f(n):
      if dp[n]!= -1:
          return dp[n]
      ans = 10**10
      if n<=0:
          return 0
      mini=n
      for i in denom:
          if (n-i)>=0:
              new = f(n-i)+1
              if new <= ans:
                  mini=i
                  ans = new
      dpl[n].append(mini)
      if mini!=n:
          dpl[n] = [item for sublist in [dpl[n], dpl[n-mini]] for item in sublist]

      dp[n]=ans

      return ans

  if __name__ == "__main__":
      ans = f(n)
      print(ans, dpl)

[pwaivers]

To be more elegant, you can remove the "dp" array. If you want to keep track of the full list, then you only need to keep track of "dpl". Here is code that I wrote and it works:

  n = 10
  denom = [1, 3, 4]
  dpl = [[] for i in range(n+1)]
  def f(n):
      if dpl[n]:
          return dpl[n]
  
      if n <= 0:
          return []

      ans = list(range(n))  # this is the max size possible
      for i in denom:
          if n-i >= 0:
              new = f(n-i) + [i]  # append i to the end of the array
              if len(new) <= len(ans):
                  ans = new

      dpl[n] = ans
      return ans

  if __name__ == "__main__":
      sol = f(n)
      print(sol)