Suma de Subconjuntos

[sinalocarlos]

Buen día Foro

No supe donde poner este hilo, espero que aquí sea el lugar correcto.


Desde mis días en la Universidad no me enfrentaba a un problema así:
Tengo una tabla con un identificador y otra columna con valores, el problema es que tengo que, a partir de un valor capturado por el usuario, calcular aquellos identificadores cuya columna valor sume dicha cantidad, la verdad cuando me pidieron eso, al escuchar la explicación tan simple, no pensé que estuviera tan complicado,obviamente pudiera calcular todos los subconjuntos dentro de la tabla pero me da miedo el siquiera calcular el numero de combinaciones posibles.

estuve investigando en Internet al respecto pero al enterarme de que se trata de el clásico ejemplo de un problema NP-Complejo, se me vinieron los ánimos al suelo, así que trate de hacer algún algoritmo que me diera una aproximación a lo que quiero pero hasta ahora no he salido de calcular aquellos subconjuntos que den la suma siempre y cuando estén contiguos.

La pregunta: han tenido experiencia con este problema o con alguna variante? si es así algún consejo?, documentación relacionada? algún truco?

Se agradece cualquier comentario
Gracias por la atención