Buscar todas las formas de sumar el número dado (con repeticiones permitidas) del conjunto dado

Question

Dado un conjunto (por ejemplo [1,2]) de n elementos y un número 'k' (por ej. 6), encuentre todas las formas posibles de generar suma = k

por ejemplo respuesta dada sería 4, porque

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

El algoritmo que podía pensar es por la fuerza bruta, simulamos todos los escenarios posibles, y se detendrá cuando de estado dado que no podemos llegar a resultados .

arr[] = [1,2] 
    k = 6 
    globalCount =0; 
    function findSum(arr,k) 
    { 
     if(k ==0) 
     globalCount++ 
     return 
     else if(k<0) 
     return 

     for each i in arr{ 
     arr.erase(i) 
     tmp = k 
     findSum(arr,tmp) 
     while(k>=0){ 
      findSum(arr,tmp -= i) 
     } 
    } 

No estoy seguro de si mi solución es la más eficiente. Comente/corrija o muestre indicadores para mejores soluciones.

EDITAR: Realmente apreciaría si alguien me puede dar complejidad en tiempo de ejecución de mi código y su código de soln. :) Complejidad de código de mina Creo que es Big-O (n^w) w = k/avg (arr [0] .. arr [n-1])

Answer 1

Si está dispuesto a disculpar los trucos de linq de lujo, puede encontrar útil esta solución de C#. Afortunadamente, linq dice algo así como inglés. La idea es construir las soluciones, ya que k comienza desde 0 y se incrementa hasta que alcanza su valor correcto. Cada valor de k se basa en las soluciones anteriores. Sin embargo, una cosa que debes observar es asegurarte de que las nuevas "formas" que estás descubriendo no sean reordenamientos de otros. Lo solucioné solo contándolos como válidos si están ordenados. (Que era solamente una única comparación)

void Main() { 
    foreach (int[] way in GetSumWays(new[] {1, 2}, 6)) { 
     Console.WriteLine (string.Join(" ", way)); 
    } 
} 

int[][] GetSumWays(int[] array, int k) { 
    int[][][] ways = new int[k + 1][][]; 
    ways[0] = new[] { new int[0] }; 

    for (int i = 1; i <= k; i++) { 
     ways[i] = (
      from val in array 
      where i - val >= 0 
      from subway in ways[i - val] 
      where subway.Length == 0 || subway[0] >= val 
      select Enumerable.Repeat(val, 1) 
       .Concat(subway) 
       .ToArray() 
     ).ToArray(); 
    } 

    return ways[k]; 
} 

Salida:

1 1 1 1 1 1 
1 1 1 1 2 
1 1 2 2 
2 2 2 

Se utiliza un enfoque de programación dinámica y debe ser más rápido que un enfoque recursivo ingenuo. Creo. Sé que es lo suficientemente rápido como para contar la cantidad de formas de romper un dólar en unos pocos milisegundos. (242)

Answer 2

Este es un subconjunto interesante del problema de partición. De hecho, hay una solución cerrada para esto (ver here y here) si permite todos los enteros.

Haciendo algunos google para la "función de partición restringida" me dio algunas pistas. This paper ofrece una discusión bastante matemáticamente rigurosa de un par de soluciones a este problema, al igual que this one.

Desafortunadamente soy demasiado vago para codificar esto. Son soluciones bastante intensas.