if you are given an amount of cents, and a set of coin denominations...how can we tell if its impossible to amount to exactly the given amount of cents?

for example say we want to gather 8 units of value but only have coins with denomination 3 and 7, thus its not possible to make a combination that amounts to 8.

(3x + 7y = 8 , has no positive integer solutions)

so given any total , and any set of coin denominations (any # of coins)...how can we tell?

sorry if this sounds trivial...I just can't find a method that suits my need

(ie. computing every possibility won't do the job if the number of coins and total value are large)

I could think of a way to handle the situation given only 2 coins..but any more and the problem becomes unwieldy. its likely just something simple im not seeing

for example say we want to gather 8 units of value but only have coins with denomination 3 and 7, thus its not possible to make a combination that amounts to 8.

(3x + 7y = 8 , has no positive integer solutions)

so given any total , and any set of coin denominations (any # of coins)...how can we tell?

sorry if this sounds trivial...I just can't find a method that suits my need

(ie. computing every possibility won't do the job if the number of coins and total value are large)

I could think of a way to handle the situation given only 2 coins..but any more and the problem becomes unwieldy. its likely just something simple im not seeing

Last edited: