Что такое быстрый способ найти два набора с равными суммами в C++?

Question

Мне нужен эффективный способ просмотреть список наборов ints, чтобы увидеть, что любые два набора имеют одинаковую сумму. В частности, в этом случае я генерирую силовую схему списка ints, которые приводятся в качестве аргумента. Из этого набора полномочий мне нужно найти пару подмножеств, которые суммируются с одним и тем же значением.

В настоящее время я пытаюсь использовать динамический программный подход (объяснение ниже):

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() создает Powerset данного списка ints, наряду с multimap называемых сумм. Для каждого элемента в силовом наборе вычисляется его сумма. Если эта сумма еще не встречена, сумма и текущий индекс вставляются в sums. В противном случае возвращается текущий набор и тот, который уже был вставлен в sums.

Это работает. Проблема в том, что для больших размеров num_list это может занять несколько минут, если вы найдете решение. Это значительно медленнее, чем метод грубой силы, просто делающий двойной for -loop и вычисляющий суммы каждый раз, чтобы найти совпадение. Есть ли лучший способ для меня сделать это?

---

EDIT: Так что я был в состоянии решить эту проблему, перемещая мою сумму проверки шаг до того, когда Powerset фактически генерируется, итеративно проверяя все ранее введенные суммы и возвращение, если совпадение найдено. Но, как было предложено в комментариях, я также переделал описание проблемы (надеюсь) устранить ту неопределенность, которая была там первоначально.

Answer 1

Я был в состоянии решить эту проблему, переместив мой счет проверки суммы до того, когда на самом деле сгенерирован силовой набор, итеративно проверяя все ранее введенные суммы и возвращая, если совпадение найдено.