The user add the items in the cart and I need to give him the best combination of combos (sets) available for the items, so he can get the best possible price. If an item doesn't fit in a combo (set) there is no problem, he just won't get the discount in that item. The big problem that I'm stuck is with the 'minimum quantity' of each set. I didn't found one algorithm example with it. That's tricky because while one set can provide the best price, but other 2 sets that could offer a better price together can be invalidated because they don't have the amount of items required to be OK. I managed to loop through all possibilities but when there are more item it gets very slow. The problem:

Each set has:

• Minimum number of items required otherwise the set is invalid and can not be used
• Percentage discount
• Items that fit in this set (IDs)

Example:

Set 1 (min: 4, discount: 40%, acceptedIds: {1, 2, 4} )
Set 2 (min: 2, discount: 30%, acceptedIds: {2, 4, 5, 6} )
Set 3 (min: 3, discount: 25%, acceptedIds: {1, 2} )
Set 4 (min: 3, discount: 60%, acceptedIds: {4, 6} )

Input

itemsAddedInCart =
{ 
  (id: 1, price: 3), 
  (id: 1, price: 3), 
  (id: 2, price: 4), 
  (id: 4, price: 3), 
  (id: 5, price: 6), 
  (id: 6, price: 4)
}

Obs.: an insight that I had was to create a matrix with the discounts computed but didn't finished my logic. Example:

             Set 1            Set 2      ...
Item 1       $ 1.2            $ 0.6        
Item 2       ...              ...
... 

If you don't understand something please let me know.