#include <cassert>
#include <deque>
#include <iostream>
#include <vector>
// Write a program that outputs all possibilities to put + or - or nothing
// between the numbers 1, 2, ..., 9 (in this order) such that the result is
// always 100. For example: 1 + 2 + 34 – 5 + 67 – 8 + 9 = 100.
enum class Operation {
Nothing,
Add,
Substract
};
// Display the list of "+- " and its result
void display(std::vector<int> const& suite,
std::vector<Operation> const& operations,
int const target)
{
std::cout << suite[0];
for (size_t i = 0, max = operations.size(); i < max; ++i) {
switch (operations[i]) {
case Operation::Nothing: break;
case Operation::Add: std::cout << " + "; break;
case Operation::Substract: std::cout << " - "; break;
}
std::cout << suite[i + 1];
}
std::cout << " = " << target << "\n";
} // display
// Produce the next vector of Operations
// \returns "true" if a vector was produced, "false" otherwise
bool next(std::vector<Operation>& operations) {
for (Operation& o: operations) {
switch (o) {
case Operation::Nothing:
o = Operation::Add;
return true;
case Operation::Add:
o = Operation::Substract;
return true;
case Operation::Substract:
o = Operation::Nothing;
break; // loop to increment next
}
}
return false; // if we reach here, the vector is not long enough
} // next
// Given a list of integers and operations, return the total
int compute(std::vector<int> const& suite,
std::vector<Operation> const& operations)
{
assert(suite.size() == operations.size() + 1);
// 1. First pass, group by "Nothing"
std::deque<int> catenated{1, suite[0]};
for (size_t i = 0, max = operations.size(); i < max; ++i) {
if (operations[i] != Operation::Nothing) {
catenated.push_back(suite[i+1]);
continue;
}
int& last = catenated.back();
last *= 10;
last += suite[i+1];
}
// 2. Second pass, evaluate
int total = catenated[0]; catenated.pop_front();
for (Operation const& o: operations) {
switch (o) {
case Operation::Nothing: break;
case Operation::Add:
total += catenated[0]; catenated.pop_front();
break;
case Operation::Substract:
total -= catenated[0]; catenated.pop_front();
break;
}
}
if (not catenated.empty()) {
display(suite, operations, total);
for (int i: catenated) {
std::cout << i << ' ';
}
std::cout << "\n";
}
assert(catenated.empty());
return total;
} // compute
// Output the lists of "+- " which achieve the goal for the given vector and the
// given target number.
void compute(std::vector<int> const& suite, int const target) {
if (suite.empty()) { return; }
Operation const N = Operation::Nothing;
std::vector<Operation> operations{suite.size() - 1, N};
do {
if (compute(suite, operations) == target) {
display(suite, operations, target);
}
} while (next(operations));
}
int main() {
std::vector<int> vec{1, 2, 3, 4, 5, 6, 7, 8, 9};
compute(vec, 100);
return 0;
}