subset sum problem

El problema de la suma de subconjuntos (SSP) es un problema de decisión en ciencias de la computación. En su formulación más general, hay un multiconjunto de enteros y una suma objetivo , y la pregunta es decidir si algún subconjunto de los enteros suma precisamente . El problema es conocido por ser NP-completo. Además, algunas variantes restringidas de él también son NP-completas, por ejemplo:La variante en la que todas las entradas son positivas. La variante en la que las entradas pueden ser positivas o negativas, y . Por ejemplo, dado el conjunto , la respuesta es sí porque el subconjunto suma cero. La variante en la que todas las entradas son positivas, y la suma objetivo es exactamente la mitad de la suma de todas las entradas, es decir, . Este caso especial de SSP se conoce como el problema de partición.