sudosolution.cpp

#include <stdio.h>
#include <cstdlib>
#include <vector>
#include <string>

int strToNumber(const char* start, const char* stop)
{
	int sum = 0;
	for (const char* c = start; c<stop; c++)
		sum = sum * 10 + *c - 48;

	return sum;
}

std::vector<std::vector<int>> recurse(const char* start, const char* stop, int target)
{
	std::vector<std::vector<int>> results;

	// No additions of +/- signs are going to let us get to more or less
	// than +- the entire sequence read as one number
	int limit = strToNumber(start, stop);
	if (target < -limit || target > limit)
		return results;

	// Check to see if we have reached a solution
	std::vector<int> thisResult {};
	if (target == limit)
		thisResult.push_back(limit);
	else if (target == -limit)
		thisResult.push_back(-limit);

	if (!thisResult.empty())
		results.push_back(thisResult);

	// Slice and recurse to find more solutions...
	for (const char* c = start + 1; c<stop; c++)
	{
		// Read the first part as a contiguous number
		int solidSliceValue = strToNumber(start, c);

		// Recurse into the second part, trying to hit the target after adjusting
		// for the first part
		auto subResults1 = recurse(c, stop, target + solidSliceValue);
		auto subResults2 = recurse(c, stop, target - solidSliceValue);

		for (auto result : subResults1)
		{
			std::vector<int> prefixedResult {};
			prefixedResult.push_back(-solidSliceValue);
			prefixedResult.insert(prefixedResult.end(), result.begin(), result.end());
			results.push_back(prefixedResult);
		}

		for (auto result : subResults2)
		{
			std::vector<int> prefixedResult {};
			prefixedResult.push_back(solidSliceValue);
			prefixedResult.insert(prefixedResult.end(), result.begin(), result.end());
			results.push_back(prefixedResult);
		}
	}

	return results;
}

int main(int argc, char* argv[])
{
	if (argc != 2)
	{
		printf("Usage: %s [n]\n", argv[0]);
		return 0;
	}

	int n = atoi(argv[1]);

	std::string input = "";
	for (int i = 1; i < n+1; i++)
		input = input + std::to_string(i);

	auto results = recurse(input.c_str(), input.c_str() + input.length(), 100);

	for (auto result : results)
	{
		if (result[0] < 0)
			continue; // Ignore solutions that start with a minus signs
		bool first = true;
		for (int x : result)
		{
			if (!first && x>0) printf("+");
			first = false;
			printf("%i", x);
		}
		printf("\n");
	}
}