¿Cómo puedo encontrar todos los casos de combinación con un número dado?

Answer 1

Este problema se llama subconjunto de suma y es famoso por ser difícil. Sin embargo, suponiendo que las cantidades son pequeñas, podemos hacerlo.

  int how_many_ways (int [] A, int target) {
   retorno f (, objetivo, A);
 }
 int f (int i, int target, int [] A) {// cuántas formas de hacer target con A [i:]
   if (objetivo <0) devuelve 0;  //demasiado baja
   if (target == 0) devuelve 1;  // no tomes nada más
   if (i == A.length) devuelve 0;  // se quedaron sin números
   retorno f (i + 1, objetivo, A) + f (i + 1, objetivo-A [i], A);
 }

Esto parece exponencial, pero f es una función determinista de sus argumentos, y solo hay | target | * | A | argumentos diferentes para f. Entonces, si memorizamos f (es decir, si ya hemos calculado f para algunos argumentos, no lo recalcule; solo devuelva lo que ya sabemos), esto se ejecuta en tiempo O (| target | * | A |).

(Esto no viola que la suma de subconjuntos sea difícil porque el objetivo podría ser un gran número. Probablemente en su caso no lo sea).