g | x | w | all
Bytes Lang Time Link
112Python 3.8 prerelease250904T195201ZV_R
083JavaScript ES6250819T094002ZArnauld
01005AB1E250819T082203ZKevin Cr
013Jelly250820T114129ZJonathan
083Wolfram Language Mathematica250820T024216ZGreg Mar
256Python3250819T152255ZAjax1234
045Charcoal250819T091020ZNeil
011Nekomata250819T033049Zalephalp
013Vyxal250819T004348Zlyxal

Python 3.8 (pre-release), 112 bytes

Like many others I've written horribly slow code, but I've put some test cases on TIO that run in a few seconds. With this approach, it's actually shorter to return all the possible solutions rather than just one of them.

from itertools import*
def f(l,b):g=lambda r:map(sum,product(l,repeat=r));return[a for a in g(b)if b*100in g(a)]

Try it online!

Explanation

Uses the Cartesian product function from itertools. First loop through every possible sum a of b-many values from l. Then save every a for which b*100 is a possible sum of a-many values from l.

I had to use a function f(l,b) rather than a lambda expression with a big list comprehension: lambda l,b:[...] because Python doesn't let you define the helper function g using the walrus operator inside of a list comprehension (even though you can use it in a regular for loop).

JavaScript (ES6), 83 bytes

Expects (L)(B) and returns the first solution found.

L=>B=>(g=(v,n,[q,...b]=L)=>q*v>0?g(v,n,b)||g(v-q,-~n):v?n*g(!~~v*n):n==B)(100*B+.5)

Try it online!

Commented

The recursive function \$g\$ is called a first time to find a list of \$n\$ coins that sum to \$100B\$ (with no constraint on \$n\$) and a second time to find a list of \$B\$ coins that sum to \$n\$. We add \$0.5\$ to the target sum in the first pass to distinguish it from the second.

L =>            // outer function taking the list L[]
B => (          // inner function taking B
g = (           // g = recursive function taking:
  v,            //   v = target value
  n,            //   n = counter
  [ q,          //   q = next value from L[]
    ...b ] = L  //   b[] = remaining values in L[]
) =>            //
q * v > 0 ?     // if q is defined and v is positive:
  g(v, n, b) || //   1st recursive call with q ignored,
                //   using b[] for the next values
  g(v - q, -~n) //   2nd recursive call with q subtracted
                //   from v and n incremented, restarting
                //   from L[]
:               // else (end of pass):
  v ?           //   if v is not 0:
    n *         //     multiply by n the result of ...
    g(!~~v * n) //     ... a recursive call with either
                //     n if v is 0.5 (successful 1st pass)
                //     or 0 otherwise (which will return 0)
  :             //   else (target reached on 2nd pass):
    n == B      //     test whether n is equal to B
)(100 * B + .5) // initial call with 100*B+0.5 as the target

05AB1E, 10 bytes

ãOʒãOт/¹Qà

Inputs in the order \$B,list\$. Output isn't sorted and contains possibly duplicated values.

(Don't) try it online. (Will time out for every test case..)

Replacing the à with , allows it to at least output for the example test case to verify it works: Try it online. (All other test cases will still time out..)

Explanation:

ã          # Cartesian product, to get all (implicit) first input B-sized lists
           # using values of the (implicit) second input-list
 O         # Sum each inner B-sized list
  ʒ        # Filter this list of A's by:
   ã       #  Cartesian product again, to get all A-sized lists using values
           #  of the (implicit) second input-list
    O      #  Sum each inner A-sized list again
     т/    #  Divide each by 100
       ¹Q  #  Check if it equals the first input-integer
         à #  Check if any is truthy within this list for size A
           # (after which the filtered list is output implicitly as result)

Jelly, 13 bytes

ṗ§Q³ṗ§÷ȷ2iʋɗƇ

A full program that accepts the list of denominations and the initial coin count \$B\$ and prints a list of all valid coin counts \$A\$ (to only print one, add for 1 byte).

Don't try it online!, but this is a touch faster (using combinations-with replacement in place of Cartesian powers).

How?

ṗ§Q³ṗ§÷ȷ2iʋɗƇ - Main Link: L, B
ṗ             - {L} Cartesian power {B} -> all B-coin collections
 §            - sums
  Q           - deduplicate -> possible B-coin sums
            Ƈ - keep those for which:
           ɗ  -   last three links as a dyad - f(CoinSum, B):
   ³          -     program's first argument -> L
    ṗ         -     Cartesian power {CoinSum} -> all CoinSum-coin collections
          ʋ   -     last four links as a dyad - f(CoinSum-coinCollections, B):
     §        -       sums -> possible CoinSum-coin sums
      ÷       -       divide all of {those} by...
       ȷ2     -       ...10^2 = 100
         i    -       first 1-index of {B} in that or 0
              - implicit print

Wolfram Language (Mathematica), 83 bytes

e=Exponent[#,x,List]&;L_~f~B_:=SelectFirst[e@(p=Tr[x^L]^#&)@B,MemberQ[e@p@#,100B]&]

Try all test cases online! Defines a named function f that takes the list L as the first argument and the number B as the second argument.

I was motivated by trying to find code that finished quickly, and the approach uses generating functions. Using the third test case as an example: the exponents of the polynomial \$(x^2+x^5+x^{10})^3 = x^6 + 3 x^9 + 3 x^{12} + 3 x^{14} + x^{15} + 6 x^{17} + 3 x^{20} + 3 x^{22} + 3 x^{25} + x^{30}\$, namely 6,9,12,14,15,17,20,22,25,30, are the values that can be made with 3 coins from the list {2,5,10}. (The coefficients record how many ways this can be done, but we're ignoring that here.) We then want to look at the polynomials \$(x^2+x^5+x^{10})^6\$, \$(x^2+x^5+x^{10})^9\$, \$(x^2+x^5+x^{10})^{12}\$, … in turn to see if the exponent 300 ever appears.

In the code, e is a helper function that produces the list of exponents of a polynomial in x, while p is a helper function that computes polynomials of the form \$(x^2+x^5+x^{10})^3\$ where the exponents of x are from L and the power at the end is the argument of p. Then e@p@B is the list of possible candidates for \$A\$, which we need to examine by seeing whether 100B is one of the exponents of e@p@# where # is the candidate. SelectFirst finds and returns the first successful candidate, both abiding by the spec and also making the code terminate much faster.

Python3, 256 bytes

def C(l,b,a):
 q=[(l,[])]
 for l,L in q:
  if len(L)==b:
   if a==-1 or sum(L)==a:yield L
   continue
  if l:q+=[(l[1:],K)for i in range(b-len(L)+1)if sum(K:=L+[l[0]]*i)<=a or a==-1]
def f(l,b):
 for L in C(l,b,-1):
  for _ in C(l,O:=sum(L),100*b):return O

Try it online!

Charcoal, 45 bytes

FEXLθηΣEη§θ÷ιXLθλ¿¬ⅈ¿№EXLθιΣEι§θ÷κXLθμ×¹⁰⁰ηIι

Try it online! Link is to verbose version of code. Stupidly slow, so only finishes for the last two test cases on TIO. Explanation:

FEXLθηΣEη§θ÷ιXLθλ

Get all sums of lists of B elements of L.

¿¬ⅈ

Stop once an answer is found.

¿№EXLθιΣEι§θ÷κXLθμ×¹⁰⁰η

Get all sums of lists of A elements of L, and see if any of them contain 100B.

Iι

If so then output A.

49 bytes for a much faster version which can solve all of the test cases on ATO:

⊞υE⊕×¹⁰⁰η¬ιF⌊υ«≔⌊υζ⊞υEζ⊙θ∧÷λμ§ζ⁻λμ»I⌕A×Eυ§ι±¹§υη¹

Attempt This Online! Link is to verbose version of code. Explanation: Uses @alephalpha's polynomial trick to calculate which potential sums are possible and intersects the sums for B elements with the sums for A elements that sum to 100B.

⊞υE⊕×¹⁰⁰η¬ι

Start with the sums for 0 elements. We're only interested in sums that go up to 100B.

F⌊υ«≔⌊υζ⊞υEζ⊙θ∧÷λμ§ζ⁻λμ»

Calculate 100B more sets of sums, using saturation so that the values are either 0 or 1. (Interpolating Minimum(u) would reduce the byte count by a further 4 but makes the code too slow for the last test case to finish on ATO.)

I⌕A×Eυ§ι±¹§υη¹

Output those sums of B that can have sums of 100B. These are the 1 entries in the vectorised product of the Bth row and 100Bth column.

Nekomata, 11 bytes

$ŧ∑ᵖ{ŧ∑'d/=

Attempt This Online!

Extremely slow. Time out for almost every test case.

$ŧ∑ᵖ{ŧ∑'d/=     Input: L, B
$ŧ              Find a B-tuple of elements of L
  ∑             Sum
   ᵖ{           Check that the sum A satisfies:
     ŧ              Find an A-tuple of elements of L
      ∑             Sum
       'd/          Divide by 100
          =         Check that it is equal to B

By default, Nekomata will find all possible solutions, possibly with duplicates. You can use the -1 flag to find only the first solution. Even with this flag, it still times out for all test cases except the last two.


Nekomata, 16 bytes

ŧ∑ũ§Ħvřʳ×§'d*@Z¿

Attempt This Online!

Longer but faster. At least it can find some (not all) solutions in a reasonable time for all test cases.

If you have a list of positive integers \$L = [a_1, a_2, \ldots, a_n]\$, and you want to check if there is a \$k\$-tuple of elements of \$L\$ that sums to \$m\$, a fast way to do this is to take the \$k\$-th power of the polynomial \$x^{a_1} + x^{a_2} + \cdots + x^{a_n}\$, and check if the coefficient of \$x^m\$ is nonzero.

ŧ∑ũ§Ħvřʳ×§'d*@Z¿        Input: B, L
ŧ                       Find a B-tuple of elements of L
 ∑                      Sum
  ũ                     Uniquify the possible results
                        (This is not necessary, but it speeds up the search)
                        Let's say the sum is A
   §Ħ                   Make a histogram of the elements of L
                        e.g., [2,5,10] -> [0,0,1,0,0,1,0,0,0,0,1]
     vř                 Replicate the histogram A times
       ʳ×               Fold by convolution
         §'d*           Multiply B by 100
             @          Take the n-th element of the result of the convolution
              Z         Check that it is nonzero
               ¿        If so, return A

The last two test cases will time out if you are trying to find all solutions. You can add the flag -l 10 to find at most 10 solutions.

Vyxal, 13 bytes

↔Ṡ'¹↔Ṡ⁰₁*=a;h

Try it Online!

Will time out online for every test case, so you'll have to read the explanation to verify correctness. Takes L then B.

Explained

↔Ṡ'¹↔Ṡ⁰₁*=a;h­⁡​‎‎⁡⁠⁡‏⁠‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁣‏⁠‎⁡⁠⁣⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁤‏⁠‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏⁠‎⁡⁠⁢⁤‏⁠‎⁡⁠⁣⁡‏⁠‎⁡⁠⁣⁢‏‏​⁡⁠⁡‌⁢⁣​‎‎⁡⁠⁣⁣‏‏​⁡⁠⁡‌⁢⁤​‎‎⁡⁠⁤⁡‏‏​⁡⁠⁡‌­
↔              # ‎⁡Generate all B-sized combinations of L with replacement
 Ṡ             # ‎⁢Summate each combination - this gives candidates for values of A
  '        ;   # ‎⁣Keep A's where the result of the following is truthy:
   ¹↔          # ‎⁤  Generate all A-sized combinations of L with replacement (this is why it'll time out for everything)
     Ṡ         # ‎⁢⁡  Summate each of those combinations
      ⁰₁*=     # ‎⁢⁢  Check whether each sum equals 100 * B
          a    # ‎⁢⁣  And return whether any do
            h  # ‎⁢⁤Output the first valid A
💎

Created with the help of Luminespire.