Coin change problem: limited coins, interested in number of unique ways to make change

Question

I have a task for uni, the requirements of which are as follows:

There is a collection of coins. For each non-negative integer k, there are two coins with the value 2^k, i.e. the collection of coins is {1, 1, 2, 2, 4, 4, 8, 8, ... }
For a given number, I need to write a method that returns the unique number of ways to make change for that amount, given the collection of coins.
For example, if the number passed to the algorithm is 6, the relevant collection of coins would be {1, 1, 2, 2, 4, 4}, the subsets that add up to 6 are {1, 1, 2, 2}, {1, 1, 4}, {2, 4}, {2, 4}, {2, 4} and {2, 4}, the unique subsets are {1, 1, 2, 2}, {1, 1, 4} and {2, 4}, and therefore the total unique ways is 3.
The numbers (and potential combinations) can be very large: the largest number in the tester class is 999,999,999,999,999,999 (10¹⁸ - 1), for which the expected result is 29,665,503.

It's apparent to me that the approach should involve dynamic programming. I've used DP once before (for another task where we had to maximise our returns in a 'coin game'), and I've watched lots of videos (such as MIT OCW) on dynamic programming to try and understand how we could solve this particular problem, but I'm quite stuck, with my current confusion as follows:

I'm struggling to understand how we can frame this problem in terms of minimising or maximising something, and therefore how to structure the recurrence relationship. As opposed to trying to determine the minimum number of coins, we're interested in all combinations that work.
There's also the issue that we (I think?) need to keep track of the solutions themselves, otherwise we won't be able to filter out duplicates.
Although it may become apparent as I work out the recurrence relation and how it should be memoized, I feel like space will be an issue: wouldn't we need something like a Z*|C| (where |C| is the size of the array of coins) sized array to store our memoized results? For a Z of 10¹⁸, that array would be huge.

At the risk of making this post too long, I've tried to sketch out a few approaches, but always come down to the problem that the recurrence seems like an OR relationship. Something like:

Let z = desired amount
Let A be array of coins, and i be the index in that array
Recurrence relation: DP(i, z) = OR ( DP(i + 1, z), DP(i + 1, z - A[i]) )
                                // Unsure how to deal with this OR in actual code. We're not saying, 
                                // "Return one of these, whichever is smaller/bigger". We're saying, 
                                // "We want to know if either case works."

Or another approach where you don't actually have an array of coins, but just start at the largest power of 2 less than Z and work down:

Let z = desired amount
Let largestCoin = largestCoinLessThanZ(z) // e.g. for z = 6, largestCoin = 4

findChange(desiredSum, runningTotal, coin):
  if runningTotal + coin = desiredSum:
    [add path to pile of valid paths]

  return (  findChange(desiredSum, runningTotal + coin, coin / 2)        // using coin of this denomination once
         or findChange(desiredSum, runningTotal + coin + coin, coin / 2) // using coin of this denomination twice
         or findChange(desiredSum, runningTotal, coin / 2)               // not using coin of this denomination at all
         )

Main:
  findchange(z, 0, largestCoin)

Sorry for the janky pseudocode - just trying to convey how I've approached it in my head.

In summary, I'm hoping for help understanding the recurrence relationship to solve this problem, and how to deal with potential space constraints. I'm working with C#, but I don't expect code - any math or pseudocode would be greatly appreciated.

user_11345521 · Answer

I think you can find a solution without going over the array multiple times, or without a O(n^2) compexity.

If you can find the closest 2^k number to your desired change, you can once again think of the remaining amount as a change and calculate the closest 2^k, and once you iterate this you will find which 2^k numbers make up this change.

Let me give an example, your number is 290, the closest 2^k is 256(2^8). The remaining is 34, the closest 2^k is 32(2^5). The remaining is 2 so 2^1.

Once you find these:[2^8,2^5,2^1] you can now find the possible combinations that make up those.

{1,1,2,2,4,4,8,8,16,16,32,32,64,64,128,128}(numbers)

{1,2,3,4,5,6,7,8, 9 ,10,11,12,13,14, 15 ,16}(indexes)

So if you want to find the combinations for 256-2^8 there are multiple possibilities:

15 + 16
15 + (13 + 14)
15 + (13 + (11 + 12))
15 + (14 + (11 + 12))
16 + (13 + 14)
16 + (13 + 14)
16 + (13 + (11 + 12))
16 + (14 + (11 + 12))

If you notice, the first 12 elements dont make 128, similarly the first 14 elements add up to 254 which doesnt make up to 256. So the combinations are limited.

You just have to ensure that the same element isn't used in both 2^8 and 2^5.

Hope this helps.

user_11345521 · Answer

    Numbers: 1 1 2 2 4 4 8 8 16 16 32 32 64 64 128 128
    Indexes: 1 2 3 4 5 6 7 8 9  10 11 12 13 14 15  16



Number  Count Combinations  
1        2    [1][2]
2        3    [4][3][2,1] 
4        5    [6][5][4,3][4,2,1][3,2,1]
8        9    [8][7][6,5][6,4,3][5,4,3][6,4,2,1][6,3,2,1][5,4,2,1][5,3,2,1]
16       17   [10] [9]  [8,7] [8,6,5] [8,6,4,3] [8,5,4,3] 

(Combinations for 16 cont.)
[8,6,4,2,1] [8,6,3,2,1] [8,5,4,2,1] [8,5,3,2,1] [7,6,5] [7,6,4,3] [7,5,4,3] 
[7,6,4,2,1] [7,6,3,2,1] [7,5,4,2,1] [7,5,3,2,1]

So, the formula is 2^(k) + 1

Try 16 for example, 16 is 2^4, so 2^(4) + 1 = 17

Or just +1 for the number you want to find the combinations for. If the number is 256 it's combinations will be 257.

Coin change problem: limited coins, interested in number of unique ways to make change

2 Answers