TADM2E 3.12

From Algorithm Wiki
Revision as of 21:37, 24 January 2019 by Butler34 (Talk | contribs)

Jump to: navigation, search

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.

This above solution assumes that there is only a single subset of S that adds to k.