[Enunciado] Queremos provar que o problema subset sum tem estrutura recursiva.
Suponha que a instância (p, n, c) do problema subset sum tem solução.
Então existe um subconjunto X de 1 .. n
que acerta o alvo
,
ou seja, satisfaz p(X) = c.
Quero provar que X é solução da instância (p, n−1, c)
ou X − {n} é solução da instância
(p, n−1, c − p[n]).
CASO 1: n ∉ X. Então X é um subconjunto de 1 .. n−1. Como p(X) = c, temos imediatamente que X é solução da instância (p, n−1, c).
CASO 2: n ∈ X. Então X − {n} é um subconjunto de 1 .. n−1. Além disso, p(X − {n}) = p(X) − p[n] = c − p[n]. Logo, X é solução da instância (p, n−1, c − p[n]).