Dollar Divisibility and Perfect Change

Question

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.

Your task

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

Answer 1

Haskell, 132 109 bytes

n?y@(x:z)|n>0=map(x:)((n-x)?y)++n?z
n?_=[[]|n==0]
(x:n)#y=n#y||n#(y-x)
_#y=y==0
x%z=[y|y<-[1..x],all(#y)$x?z]

Try it online!

Explanation

This is a pretty straight-forward solution to the puzzle.

• (?) takes an amount and a list of denominations and determines all ways to make the amount with the given denominations. Solutions are sorted in the same order as the original denomination list.

  This is just all the possible sets we could have in our pocket.

• (#) an amount and a list of amounts and determines if the amount is the sum of a sub-list of the given list.

  This is whether an amount can be made from a given set of bills.

• (%) is the main function. It takes an amount, x, and a list of denominations, z. For each amount, y, from 1 to the given amount it checks that for every way to make the initial amount (x?z), y is the sum of some sub-list of it.

Answer 2

Python 2, 200 197 193 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}

Answer 3

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)

Answer 4

Wolfram Methematica, 104 bytes

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

Ungolfed (read from the end):

Rest@* // Removing 0
  Intersection@@   // Intersecting all totals
     Map[Total]/@  // Counting total of each subset
        Subsets/@  // Getting all the subsets of each partition
           Union[  // Removing duplicates 
              Sort/@ // Sorting each partition (to remove duplicates next)
                 IntegerPartitions[#,#,PadLeft[{},Length[#2]#,#2]] // Getting all Integer partitions
                ]&