#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; catenated.push_back(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;
		}
	}
	
	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;
}