num_ways recursion example

ways.cpp

#include <iostream>
#include <vector>

/* create a function that does the following:
 * `num_ways(total, ways)`
 *   - total is an integer
 *   - ways is a list of integers
 * "Total is a number you want to get to and ways is the types of numbers
 * you can add to get to the total. The function should return a list
 * of lists that contains a series integers that add up to the total
 * and each list should be a unique combination. Also, another rule
 * is that you cannot go over the total."
 *
 * Example:
 * in: num_ways(4, [1,3,5])
 * out: [[1,1,1,1]
 *       [3,1]
 *       [1,3]]
 */

// Forward declare because fuck header files
void iterate(
  const int total,
  const std::vector<int>& ways,
  int acc,
  const std::vector<int>& numbers,
  std::vector<std::vector<int>>* result
);

void explore(
  const int total,
  const std::vector<int>& ways,
  int n,
  int acc,
  std::vector<int> numbers,
  std::vector<std::vector<int>>* result
) {
  // Bail out of this path if it exceeds the target
  if (acc + n > total) return;

  // Add the current number to the list
  numbers.push_back(n);

  // If we found a solution, push it to the result vector
  if (acc + n == total) {
    result->push_back(numbers);
  } else {
    // Add the current number to the accumulator
    acc += n;

    // Recurse
    iterate(total, ways, acc, numbers, result);
  }
}

void iterate(
  const int total,
  const std::vector<int>& ways,
  int acc,
  const std::vector<int>& numbers,
  std::vector<std::vector<int>>* result
) {
  for (auto n : ways) {
    explore(total, ways, n, acc, numbers, result);
  }
}

std::vector<std::vector<int>>* num_ways(
  const int total,
  const std::vector<int>& ways
) {
  auto result = new std::vector<std::vector<int>> {};
  iterate(total, ways, 0, {}, result);
  return result;
}

int main() {
  auto result = num_ways(30, {1, 3, 5});
  for (auto i = 0; i < result->size(); i++) {
    for (auto j = 0; j < result->at(i).size(); j++) {
      std::cout << result->at(i).at(j);
      if (j < result->at(i).size() - 1) std::cout << " + ";
    }
    std::cout << std::endl;
  }

  return 0;
}