Сумма подмножества C++ 2^n/ошибка рекурсии/уточнение

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

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

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

Проблема, с которой я столкнулся с этим кодом, заключается в следующем :, а не в 2^n времени (, что правильно для такой реализации, когда результаты не найдены, не так ли? )выполняется за [2^ (n+1 )] -1 раз; O (2^n ), как указано в комментарии.Я понимаю, почему это дано, когда я проверяю (runningTotal == targetTotal )на более глубоком уровне, чем мог бы, по сути добавляя дополнительную глубину сам, не так ли? Я пытался смоделировать базовый случай как можно точнее, дайте мне знать, если вы обнаружите какие-либо «запахи кода». Должен ли я сломаться, как только увижу, что (runningTotal + учтите )== targetTotal?

Примечание. :Я не думаю, что это относится к "Просмотру кода", поскольку я спрашиваю о конкретной строке кода, а не об общем подходе (если мне нужно изменить подход, так и быть, я делаю это, чтобы учиться ).

Вот моя попытка (- это "проходимый" C/C++, если не считать упомянутого выше отсутствия оптимизации?):

#include <iostream>
using namespace std;
bool setTotalling(int chooseFrom[], int nChoices, int targetTotal,
    int chooseIndex, int runningTotal, int solutionSet[], int &solutionDigits,
    int &nIterations) {
  nIterations++;
  if (runningTotal == targetTotal) {
    return true;
  }
  if (chooseIndex >= nChoices) {
    return false;
  }
  int consider = chooseFrom[chooseIndex];
  if (setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex + 1,
      runningTotal + consider, solutionSet, solutionDigits, nIterations)) {
    solutionSet[solutionDigits++] = consider;
    return true;
  }
  if (setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex + 1,
      runningTotal, solutionSet, solutionDigits, nIterations)) {
    return true;
  }
  return false;
}
void testSetTotalling() {
  int chooseFrom[] = { 1, 2, 5, 9, 10 };
  int nChoices = 5;
  int targetTotal = 23;
  int chooseIndex = 0;
  int runningTotal = 0;
  int solutionSet[] = { 0, 0, 0, 0, 0 };
  int solutionDigits = 0;
  int nIterations = 0;
  cout << "Looking for a set of numbers totalling" << endl << "--> "
      << targetTotal << endl << "choosing from these:" << endl;
  for (int i = 0; i < nChoices; i++) {
    int n = chooseFrom[i];
    cout << n << ", ";
  }
  cout << endl << endl;
  bool setExists = setTotalling(chooseFrom, nChoices, targetTotal, chooseIndex,
      runningTotal, solutionSet, solutionDigits, nIterations);
  if (setExists) {
    cout << "Found:" << endl;
    for (int i = 0; i < solutionDigits; i++) {
      int n = solutionSet[i];
      cout << n << ", ";
    }
    cout << endl;
  } else {
    cout << "Not found." << endl;
  }
  cout << "Iterations: " << nIterations << endl;
}
int main() {
  testSetTotalling();
  return 0;
}