Was ist ein schneller Weg, um zwei Sätze mit gleichen Summen in C++ zu finden?

Question

Ich brauche eine effiziente Art und Weise durch eine Liste von Sätzen von ints zu suchen alle zwei Sätze die gleiche Summe zu sehen. In diesem Fall erzeuge ich das Powerset einer Liste von Ints, die als Argument übergeben werden. Von diesem Powerset muss ich ein Paar Teilmengen finden, die auf den gleichen Wert summieren.

Derzeit bin ich versucht, eine dynamische Programmierung Ansatz (Erklärung unten) zu verwenden:

typedef std::vector<int> intvec; 
typedef std::vector<std::vector<int> > intvecvec; 
typedef std::multimap<int,int> intmap; 

/* Functions previously shown here that were removed: 
* intvecvec search_for_sum(intvec num_list) 
* and 
* int sum_exists(std::vector<intvec> pset, int index, intmap &sums) 
*/ 

/* This function was previously just called powerset(), and wasn't 
* shown because the problem wasn't happening here. After refactoring, 
* I removed the functions that were shown here previously and simply 
* iteratively checked for sum matches while generating the powerset 
*/ 
intvecvec powerset_search(intvec num_list) 
{ 
    intvecvec result; 
    std::multimap<int, intvec> power_set; 
    for (int c = 0; c < pow(2, num_list.size()); c++) { 
     intvec temp; 
     for (int i = 0; i < num_list.size(); i++) { 
      if (c & (1 << i)) { 
       temp.push_back(num_list.at(i)); 
      } 
     } 
     int sum = std::accumulate(temp.begin(), temp.end(), 0); 
     std::multimap<int, intvec>::iterator it = power_set.find(sum); 
     if (it == power_set.end()) { 
      power_set.insert(std::make_pair(sum, temp)); 
     } else { 
      result.push_back(it->second); 
      result.push_back(temp); 
      break; 
     } 
    } 
    return result; 
} 

search_for_sum() schafft die Powerset der gegebenen Liste von ints, zusammen mit multimap genannt Summen. Für jedes Element im Powerset wird seine Summe berechnet. Wenn diese Summe noch nicht gefunden wurde, wird die Summe und der aktuelle Index in sums eingefügt. Andernfalls wird der aktuelle Satz und der, der bereits in sums eingefügt wurde, zurückgegeben.

Dies funktioniert. Das Problem ist, dass für große Größen von num_list dies ein paar Minuten dauern kann, um mit einer Lösung zurückzukehren, wenn es eine gibt. Dies ist wesentlich langsamer als die Brute-Force-Methode, bei der man einfach eine doppelte for-Schleife macht und jedes Mal aufsummiert, um eine Übereinstimmung zu finden. Gibt es einen besseren Weg für mich?

---

EDIT: So konnte ich diese meine Summe Prüfung durch Bewegungsschritt lösen bis zu, wenn die Potenz tatsächlich erzeugt wird, iterativ alle zuvor eingegebenen Summen überprüft und der Rückkehr, wenn eine Übereinstimmung gefunden wurde. Aber wie in den Kommentaren gefordert, habe ich auch die Problembeschreibung überarbeitet, um (hoffentlich) die anfängliche Vagheit zu beseitigen.

Answer 1

Ich konnte diesen Schritt meiner Summenprüfung, indem bis lösen, wenn die Potenz tatsächlich erzeugt wird, iterativ alle zuvor eingegebenen Summen überprüft und die Rückkehr, wenn eine Übereinstimmung gefunden wurde.