Si en el ejercicio 3 de la hoja de problemas de divide y vencerás hacemos un pequeño cambio permitiendo hacer variable el número de datos que tienen que sumar una cantidad dada, el problema es sensiblemente más “difícil”:

Dado un conjunto S de enteros y un entero x, ¿existe algún subconjunto de S cuya suma sea x?

Es el problema conocido como la suma de subconjuntos, puede verse como un caso particular del problema de la mochila (no fraccionable), y el mejor algoritmo exacto conocido para resolverlo tiene coste exponencial.

Veremos una solución (de coste pseudo-polinómico) en el siguiente tema sobre algoritmos de programación dinámica.