Online PHP editor | refs for SXnXt

<?php class Sums { public function getAllSums($total) { if ($total < 0) { return array(); } $return = array(); // Reducing the problem linearly, examining one integer at a time for ($i = $total; $i >= 1; $i--) { $subTotal = $this->getSumsFor($i, $total); foreach ($subTotal as $item) { $return[] = $item; } } return $return; } private function getSumsFor($currentValue, $total) { $return = array(); // Base case where the current iteration is its own sum if ($currentValue == $total) { $return[] = array($total); return $return; } // Base case where we have all the 1's summed up else if ($currentValue == 1) { $sum = array(); for ($i = 0; $i < $total; $i++) { $sum[] = 1; } $return[] = $sum; return $return; } $remainder = $total - $currentValue; // Break the problem into a smaller chunk $possibleSums = $this->getAllSums($remainder); foreach ($possibleSums as $row) { // Once we have the sum of the remainder, add the original value back array_unshift($row, $currentValue); $return[] = $row; } return $return; } } $sums = new Sums(); echo '<pre>'; print_r($sums->getAllSums(4)); echo '</pre>';