Algorithm · Google · Hard
You are given an array dp in which dp[i] stores how many distinct ways there are to make total amount i using a set of coin denominations. Reconstruct the possible coins array that produced this dp array. You may assume exactly one coin set can generate the supplied dp values. Input: dp, where dp[i] is the count of ways to form amount i. Output: Return the recovered array coins containing the coin denominations. Example Input: dp = [1, 1, 2, 2, 3, 4] Output: [1, 2, 5]…