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

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

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

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

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

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

Здесь моя попытка (есть ли этот "passable" 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;
}