From The Algorithm Design Manual Solution Wiki
Jump to navigation Jump to search

Let's put into the black box whole set . If is True, then such a subset exists and we can go on:

  1. R:=S
  2. for i:=1 to n do
    1. If is True then

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