# An algorithm for finding subset matching criteria?

I recently came up with a problem which I would like to share some thoughts about with someone on this forum. This relates to finding a subset. In reality it is more complicated, but I tried to present it here using some simpler concepts.

To make things easier, I created this conceptual DB model:

Let's assume this is a DB for storing recipes. Recipe can have many instructions steps and many ingredients.

Ingredients are stored in a cupboard and we know how much of each ingredient we have.

Now, when we create a recipe, we have to define how much of each ingredient we need. When we want to use a recipe, we would just check if required amount is less than available amount for each product and then decide if we can cook a dinner - if amount required for at least one ingredient is less than available amount - recipe cannot be cooked. Simple sql query to get the result.

This is straightforward, but I'm wondering, how should I work when the problem is stated the other way round, i.e. how to find recipies which can be cooked only from ingredients that are available?

I hope my explanation is clear, but if you need any more clarification, please ask.

• Keeping it at a conceptual level, if your SQL query is sufficiently "set-based", you should be able to apply it to the whole Recipe table at once. Jul 24, 2014 at 12:16
• @AakashM What do you mean by saying "sufficiently set based"? Jul 24, 2014 at 12:32
• see eg this, this, this. So if it's a single statement that just needs to be supplied a `Recipe.ID`, it could probably be made to work against the whole of `Recipe` at once; but if it's some `CURSOR`-based or other looping code, it would need another loop around it (ugh) Jul 24, 2014 at 13:13
• I don't think I've got the question completely, but how about iterating through each recipe and flag possible to cook or not? If the end result required is a list of recipes which could be cooked. Or did you mean to say all possible combinations of recipes that can be cooked simultaneously ie 'without replacement' of ingredients after cooking one recipe, as we say in combination/probability math questions?
– dbza
Jul 24, 2014 at 21:04
• In that case this is not so hard, Im adding the SQL. Ideally noboby should be giving you ready-made answers and spoiling your fun learning experience :)
– dbza
Jul 26, 2014 at 0:21

After your clarifications on the question, I would go by this logic to list recipeids excluding any recipe with a missing/insufficient ingredient.

``````SELECT recipeid
FROM recipeingredients RI
WHERE recipeid NOT IN (SELECT RI1.recipeid
FROM recipeingredients RI1
LEFT OUTER JOIN Ingredients I ON RI1.ingredientsid = I.id
AND RI1.Requiredquantity <= I.availablequantity
WHERE I.id IS NULL
)
``````

Reasonably simple, using a subquery join.

1. JOIN Recipeingredients on Ingredients where RequiredQuantity less or equal AvailableQuantity. Test this to make sure it works as expected.
2. JOIN Recipe IN above subquery to find those you can make.

I'll leave you to write the actual SQL.