<?php

//--------------------------------------------------
// Return the required values for this script

	$numbers = returnSubmittedValue('numbers', 'POST');
	$goal = returnSubmittedValue('goal', 'POST');

//--------------------------------------------------
// Clean goal

	$goal = trim($goal);
	$goal = preg_replace('/[^0-9\.\-]/', '', $goal);
	$goal = floatval($goal);

//--------------------------------------------------
// Convert numbers into an array

	$cleanNumbers = array();

	$numbers = explode("\n", $numbers);

	// set_time_limit(0);

	if ($goal == 0) {
		$numbers = array_slice($numbers, 0, 10); // Maximum, any more the page gets too big (1,023 calculations)
	} else {
		$numbers = array_slice($numbers, 0, 15); // Maximum, any more it takes too long to process (32,767 calculations)... 20 = ~6 seconds, 22 = ~25 seconds (max time = X unique numbers, goal being the sum of X).
	}

	foreach ($numbers as $cNumber) {

		$cNumber = trim($cNumber);
		$cNumber = preg_replace('/[^0-9\.\-]/', '', $cNumber);
		$cNumber = floatval($cNumber);

		if ($cNumber != 0) {
			$cleanNumbers[] = $cNumber;
		}

	}

	$numbers = implode("\n", $cleanNumbers);

//--------------------------------------------------
// Main function

	function numberAdditions($numbers, $goal = NULL) {

		//--------------------------------------------------
		// Defaults - using a global variables is quicker
		// than returning values, and merging arrays.

			$GLOBALS['calsTotal'] = 0;

			$GLOBALS['resultsOutput'] = array();

		//--------------------------------------------------
		// If we can't possibly hit the goal

			if ($goal !== NULL && $goal > array_sum($numbers)) {
				$GLOBALS['calsTotal']++;
				return $GLOBALS['resultsOutput'];
			}

		//--------------------------------------------------
		// Run

			$usedNumbers = array();

			numberAdditionsSub($numbers, $goal, $usedNumbers);

		//--------------------------------------------------
		// Return

			return $GLOBALS['resultsOutput'];

	}

	function numberAdditionsSub($numbers, $goal, $usedNumbers) {

		foreach ($numbers as $cNumber) { // A local copy of $numbers is made, so not effected by the array_shift()

			//--------------------------------------------------
			// Stats

				$GLOBALS['calsTotal']++;

			//--------------------------------------------------
			// New usedNumbers array, and calculate its "sum"

				$newUsedNumbers = $usedNumbers;

				array_push($newUsedNumbers, $cNumber); // Faster than array_merge

				$sum = array_sum($newUsedNumbers);

			//--------------------------------------------------
			// Remove this number from the array of newNumbers.
			//
			// So firstly, when we descend into the next set
			// of numbers, we don't want this number to be
			// used again... and secondly, during the first
			// loop (at this level), we will go though every
			// combination of (remaining) children, but on
			// the second loop we do not need to include the
			// first number again, as it has already been used
			// in every combination before hand.
			//
			// e.g.
			//    1)  A
			//    2)  A + B
			//    3)  A + B + C
			//    4)  A + C
			//    5)  A + C + B   -- Dupe of 3
			//    6)  B
			//    7)  B + A       -- Dupe of 2
			//    8)  B + A + C   -- Dupe of 3
			//    9)  B + C
			//    10) B + C + A   -- Dupe of 3
			//    11) C
			//    12) C + A       -- Dupe of 2
			//    13) C + A + B   -- Dupe of 3
			//    14) C + B       -- Dupe of 9
			//    15) C + B + A   -- Dupe of 3

				array_shift($numbers);

			//--------------------------------------------------
			// Sum matches

				if ($goal !== NULL && $sum == $goal) {

					//--------------------------------------------------
					// Match

						$GLOBALS['resultsOutput'][] = implode(' + ', $newUsedNumbers) . '  = ' . $sum; // two spaces before equals to help sorting

				} else if ($goal === NULL || $sum < $goal) {

					//--------------------------------------------------
					// Add to output, if there is no goal to match

						if ($goal === NULL) {
							$GLOBALS['resultsOutput'][] = implode(' + ', $newUsedNumbers) . '  = ' . $sum; // two spaces before equals to help sorting
						}

					//--------------------------------------------------
					// Process remaining numbers as children

						numberAdditionsSub($numbers, $goal, $newUsedNumbers);

				}

		}

	}

//--------------------------------------------------
// Process

	$timeStart = explode(' ', microtime());
	$timeStart = ((float)$timeStart[0] + (float)$timeStart[1]);

	if ($goal != 0) {
		$output = numberAdditions($cleanNumbers, $goal);
	} else {
		$output = numberAdditions($cleanNumbers);
	}

	$timeEnd = explode(' ', microtime());
	$timeEnd = ((float)$timeEnd[0] + (float)$timeEnd[1]);

	$timeTotal = round(($timeEnd - $timeStart), 3);

//--------------------------------------------------
// Output

	$htmlOutput = '';

	foreach ($output as $cNumber) {
		$htmlOutput .= preg_replace('/ += ([^ ]+)$/', ' = <strong>$1</strong>', html($cNumber)) . "<br />\n";
	}

	if ($GLOBALS['calsTotal'] > 0) {

		if ($htmlOutput != '') {
			$htmlOutput .= "<br />\n";
		}

		$htmlOutput .= 'Results: ' . count($output) . "<br />\n";
		$htmlOutput .= 'Calculations: ' . number_format($GLOBALS['calsTotal']) . "<br />\n";
		$htmlOutput .= 'Time: ' . $timeTotal;

	}

?>