# select subset of combinations based on condition

My question is about choosing a subset of combinations within a list, based on a condition.

Fot example, a shop sells 26 products. The name of a product starts with a letter. Each product has a price. For example, the customer pays 1 dollar for product 'a'. The product-price range for this shop looks like:

shop = {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {g, 7}, {h,
8}, {i, 9}, {j, 10}, {k, 11}, {l, 12}, {m, 13}, {n, 14}, {o,
15}, {p, 16}, {q, 17}, {r, 18}, {s, 19}, {t, 20}, {u, 21}, {v,
22}, {w, 23}, {x, 24}, {y, 25}, {z, 26} };


A customers visit a store with 30 dollar in his pocket.The customer wants to know all combinations of products he can buy for 30 dollar, or less.

For example: {{z, 26},{d, 4}},{{z, 26},{c, 3}},{{z, 26},{b, 2}}....{{j, 10},{t, 20}}

I tried to use 'Subsets' to find als possible combinations. Then I get a error:

test = Subsets[shop];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]


\$RecursionLimit::reclim2: Recursion depth of 1024 exceeded during evaluation.

When I made a smaller selection (for example the first 8 products) it works fine.

test = Subsets[shop[[1 ;; 8]]];
test1 = {#, Sum[i, {i, #}]} & /@ test;
Select[test1[[All, 2]][[2 ;; -1]], #[[2]] < 30 &]


Who has a solution for this problem? Or a different approach?

The key part here is using FrobeniusSolve.

shop = {{a,1},{b,2},{c,3},{d,4},{e,5},{f,6},{g,7},{h,8},{i,9},{j,10},{k,11},{l,12},{m,13},{n,14},{o,15},{p,16},{q,17},{r,18},{s,19},{t,20},{u,21},{v,22},{w,23},{x,24},{y,25},{z,26}};

money = 30;
(*All combos with possibly multiple of each*)FrobeniusSolve[shop[[;; , 2]], money];
(*If the store only has one of each item*) Pick[shop, #, 1] & /@ Select[%, Max[#]==1 &]


{{{n, 14}, {p, 16}}, {{m, 13}, {q, 17}}, <<288>>, {{a, 1}, {b, 2}, {c, 3}, {d, 4}, {e, 5}, {f, 6}, {i, 9}}}

• Nice answer, Thanks. In the case, de prices are not integers,for example shop = {{a,1.1},{b,2.2},{c,3.3},{d,4.4},{e,5.5},{f,6.6}}, this formula doesn't work. What do you suggest for this situations? Dec 3, 2021 at 8:24
• @MichielvanMens Sorry for the late response, but I would first convert everything to pennies so you're working with integers again and can still use FrobeniusSolve. Then, as a first approach, I would simply map over the range (i.e. one by one). I did a quick and dirty test and it was actually rather quick. Dec 12, 2021 at 0:45