# Dollar Divisibility and Perfect Change

I have $15 in my pocket. Likewise, I am in a store which doesn't give change. While browsing, I spot an item that costs$10 (tax included). Can I buy that item without losing any money?

In this case, the answer is yes. No matter how my $15 is divided up (one 10 and one 5, or three 5s, or something else), I will always have the exact$10 needed.

As a second example, I have $0.16 in my pocket. What other amounts of money must I be able to pay exactly? Possible Divisions: 0.01, 0.05, 0.10 0.01, 0.05 x 3 0.01 x 16 Guaranteed Exact Change: 0.01, 0.05, 0.06, 0.10, 0.11, 0.15, 0.16  What if I have$0.27 in my pocket?

Possible Divisions:
0.01 x 2, 0.25
0.01 x 2, 0.05, 0.10 x 2
0.01 x 2, 0.05 x 3, 0.10
0.01 x 2, 0.05 x 5
0.01 x 27
Guaranteed Exact Change:
0.01, 0.02, 0.25, 0.26, 0.27


In the above case, there were only a few amounts of money for which I would always have perfect change.

Write the shortest program (or named function) which takes A) an integer amount of money and B) a list of possible denominations as input, and outputs a list of the amounts of money for which I must have perfect change. Input can be either STDIN or arguments for the program or function. I'm not going to be super-strict on input formatting; it can match how your language formats arrays.

## Perhaps a More Detailed Explanation

I have a certain amount of money in my pocket, which is formed from a set of possible demonstrations of currency. If I have $8, and I know that the possible denominations are$2 and \$3, then there's only so many different combinations of bills that could be in my pocket. These are 2+2+2+2 and 3+3+2. In order to be able to produce an exact amount of money, I have to be able to produce that quantity using the only the bills that are in my pocket. If I had four 2s, I could produce 2, 4, 6, or 8. If I had two 3s and a 2, I could produce 2, 3, 5, 6, or 8 Since I don't know which of these combinations I actually have in my pocket, my final answer is reduced to 2, 6, 8. These are the values I know I could produce from my pocket, given the total amount and the possible denominations.

## Hand-Calculated Example I/O

7 [3, 4]
3, 4, 7        //only one possible division into 3 + 4

7 [3, 2]
2, 3, 4, 5, 7  //the only division is 3 + 2 + 2

6 [2, 3, 4]
6     //divisions are 2+2+2, 3+3, 2+4

16 [1, 5, 10, 25]          //this represents one of the examples above
1, 5, 6, 10, 11, 15, 16

27 [1, 5, 10, 25]          //another example from above
1, 2, 25, 26, 27

1500 [1, 5, 10, 25, 100, 500, 1000, 2000]
500, 1000, 1500

600 [100, 500, 1000, 2000]
100, 500, 600

600 [200, 1, 5, 10, 25, 100, 500, 1000, 2000]
600

• This is very unclear. – motoku Feb 27 '15 at 1:30
• @FryAmTheEggman I have added a "perhaps a more detailed explanation." Let me know if it is still confusing. (I also removed an edge case because it was pretty much pointless.) – PhiNotPi Feb 27 '15 at 2:42
• I don't see how you're getting 6 [2, 3, 4]. Can't 2+2+2 not make 3, and 3+3 not make 2 and 4? – xnor Feb 27 '15 at 7:44
• @xnor you are correct, fixed. – PhiNotPi Feb 27 '15 at 12:42
• Should the program run in reasonable time for all the inputs? E.g. my shortest idea is exponential in the starting amount and 2^1500 is a lot of anything. – randomra Feb 28 '15 at 5:21

# Python 2, 200197193 140 bytes

f=lambda n,D,S={0}:sum([f(n-x,D,S|{x+y for y in S})for x in D],[])if n>0else[S]*-~n
g=lambda*a:(f(*a)and reduce(set.__and__,f(*a))or{0})-{0}


(Thanks to @Nabb for tips)

Here's a poorly golfed solution for now to get things started. Call with g(16, [1, 5, 10, 25]) — output is a set with the relevant denominations.

The approach is straightforward, and is broken down into two steps:

• f looks at all ways of reaching n with denominations D (e.g. [1, 5, 10]), and for each one it works out all amounts that can be made with these denominations (e.g. set([0, 1, 5, 6, 10, 11, 15, 16])).
• g calculates the intersections of the results of f, then removes 0 for the final answer.

The program solves cases 1-5 and 7 fine, stack overflows on 6 and takes forever on 8.

If there is no solution (e.g. g(7, [2, 4, 6])), then the program returns an empty set. If an error is allowed to be thrown for such a case, then here is a shorter g:

g=lambda*a:reduce(set.__and__,f(*a))-{0}

• g=lambda L,c=0:L and g(L[1:],c)|g(L,c+L.pop(0))or{c} is a little shorter – Nabb Mar 1 '15 at 8:18
• A bit more by moving -{0} into g and using [L]*-~n instead of [L][-n:] – Nabb Mar 1 '15 at 8:34

# JavaScript (ES6) 162 203 207

Edit Changed the way to intersect result sets in array r. A bit faster, but the algorithm still stinks.

More detailed explanation will follow.
Shortly : c is a recursive function that enumerate all the possible subdivisions. k is a recursive function that enumerate all the possible sums without repetitions. Any new result set found with k function is compared with the previous set found, only the common results are kept.

Why is it so slow? Having to manage a target total of, say, 1500 and a single piece of value 1, enumerating all the possibile sums is not a good idea.

F=(s,d,r,
c=(s,i,t=[],v,k=(i,s,v)=>{for(;v=t[i++];)k(i,s+v);o[s]=s})=>
{for(s||(i=k(o=[],0),r=(r||o).filter(v=>o[v]));v=d[i];++i)s<v||c(s-v,i,[...t,v])}
)=>c(s,0)||r


Ungolfed

F=(s,d)=>{
var r
var c=(s,i,t=[])=>
{
var o=[],v
var k=(i,s)=> // find all sums for the current list t, set a flag in the o array
{
var v
for(;v=t[i++];)k(i,s+v)
o[s]=s
}

if (s==0) {
k(0,0)
if (r)
r = r.filter(v=>o[v]) // after first loop, intersect with current
else
r = o.filter(v=>v) // first loop, keep all results
}
else
for(;v=d[i];++i)
{
if (s >= v)
c(s-v, i, t.concat(v))
}
}
c(s,0) // enumerate all possible set of pieces
return r
}


Test In Firefox/FireBug console

F(16,[1,5,10,25])


[1, 5, 6, 10, 11, 15, 16]

(time 84 msec)

F(27, [1, 5, 10, 25])


[1, 2, 25, 26, 27]

(time 147252 msec, so not sooo fast)

## Wolfram Methematica, 104 bytes

Rest@*Intersection@@Map[Total]/@Subsets/@Union[Sort/@IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]]]&


Rest@* // Removing 0