3.27

Let's put into the black box whole set $S=\{x_{i}\}_{i=1}^{n}$. If $bb(S)$ is True, then such a subset exists and we can go on:

1. R:=S
2. for i:=1 to n do
   1. If $bb(R/\{x_{i}\})$ is True then $R:=R/\{x_{i}\}$

When this iteration is finished R will be subset of S that adds up to k.

Above solution works even when there are multiple subsets that add up to k.

Back to Chapter 3