# Subset Sum Problem

Computer Science Level 3

Little Timmy's grandmother gave him 5 black stones and 4 gray stones ​and told him to find a group of black stones that weigh the same as a group of gray stones. If he can find these groups, he should put them on his window sill to bring calmness into his life. Otherwise, he'll have to fetch more stones. To do this, Timmy decides to ask his mom for a balance to undertake the task. Although he doesn't know this, the set of weights, in pounds, for each stone is the following:

$$B = \{3, 8, 5, 5, 2\}$$

$$G = \{4, 9, 7, 6\}$$

Will Timmy find two groups of stones that weigh the same? If so, is will this problem take polynomial-time, meaning that it is in $$P$$, and can also be solved using non-deterministic polynomial-time, meaning that it is also in $$NP$$; or can he solve it only using non-deterministic polynomial-time algorithms, meaning that it is only in $$NP$$? Think about the amount of calculations performed for each stone to figure out if the problem is in $$P$$ and $$NP$$, or only in $$NP$$.

Can Timmy find equally weighing groups of grey and black stones?

×