algoritmo efficiente per trovare una combinazione, che somma è uguale a un numero noto, in un insieme del numero

Question

Diciamo v'è un insieme di numero

1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Voglio trovare diverse combinazioni nell'insieme di numeri tale che la somma di esso è uguale a un numero noto, ad esempio 18. Possiamo scoprire che 5, 6 , 7 è abbinato (5 + 6 + 7 = 18).

I numeri in una combinazione non possono essere ripetuti e il numero in un set potrebbe non essere consecutivo.

Ho scritto un programma C# per farlo. Il programma è casuale per raccogliere il numero per formare una combinazione e verificare se la somma della combinazione è uguale a un numero noto. Tuttavia, la combinazione del programma trovato può essere ripetuta e rende il progresso non efficace.

Mi chiedo se ci sia un algoritmo efficiente per scoprire tale combinazione.

Ecco parte del mio codice.

 int Sum = 0; 
     int c; 
     List<int> Pick = new List<int>(); 
     List<int> Target = new List<int>() {some numbers} 

     Target.Sort(); 

      while (!Target.Contains(Sum)) 
      { 
       if (Sum > Target[Target.Count - 1]) 
       { 
          Pick.Clear(); 
          Sum = 0; 

       } 
       while (true) 
       { 
        if (Pick.IndexOf(c = Math0.rand(0, Set.Count - 1)) == -1) 
        { 
         Pick.Add(c); 
        } 

        //Summation Pick 
        Sum = 0; 
        for (int i = 0; i < Pick.Count; i++) 
         Sum += Set[Pick[i]]; 

        if (Sum >= Target[Target.Count - 1]) 
         break; 
       } 


      } 

      Result.Add(Pick); 

Answer 1

È possibile utilizzare la ricorsione. Per ogni dato numero nel set, trovare le combinazioni di numeri più piccoli che si aggiunge al numero:

public static IEnumerable<string> GetCombinations(int[] set, int sum, string values) { 
    for (int i = 0; i < set.Length; i++) { 
    int left = sum - set[i]; 
    string vals = set[i] + "," + values; 
    if (left == 0) { 
     yield return vals; 
    } else { 
     int[] possible = set.Take(i).Where(n => n <= sum).ToArray(); 
     if (possible.Length > 0) { 
     foreach (string s in GetCombinations(possible, left, vals)) { 
      yield return s; 
     } 
     } 
    } 
    } 
} 

Usage:

int[] set = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; 

foreach (string s in GetCombinations(set, 18, "")) { 
    Console.WriteLine(s); 
} 

uscita:

1,2,4,5,6, 
3,4,5,6, 
1,2,3,5,7, 
2,4,5,7, 
2,3,6,7, 
1,4,6,7, 
5,6,7, 
1,2,3,4,8, 
2,3,5,8, 
1,4,5,8, 
1,3,6,8, 
4,6,8, 
1,2,7,8, 
3,7,8, 
2,3,4,9, 
1,3,5,9, 
4,5,9, 
1,2,6,9, 
3,6,9, 
2,7,9, 
1,8,9, 
1,3,4,10, 
1,2,5,10, 
3,5,10, 
2,6,10, 
1,7,10, 
8,10, 

Answer 2

Un possibile metodo alternativo . Con un piccolo set come questo, potresti usare la forza bruta. Il tuo set {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ha 10 elementi e ogni elemento può essere presente o non presente. Questo può essere mappato su un numero binario compreso tra 0 (= 0b0000000000) e 1023 (= 0b1111111111). Passare in rassegna i numeri da 0 a 1023 inclusi e controllare la somma per il sottoinsieme corrispondente ai bit impostati della rappresentazione binaria del numero.

Forse non il più utile per questa particolare domanda, ma un buon modo per generare tutti i possibili sottoinsiemi di un determinato set.