Skip to content

Instantly share code, notes, and snippets.

@mjdominus
Created February 18, 2013 14:10
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mjdominus/4977692 to your computer and use it in GitHub Desktop.
How many ways are there to add up 10 numbers, each between 1 and 12, to make a total of 70?
my @f;
sub solve {
my ($n, $x) = @_;
return 1 if $x == 0 and $n == 0;
return 0 if $x <= 0 || $n == 0;
return $f[$n][$x] if defined $f[$n][$x];
my $total = 0;
for my $i (1 .. 12) {
$total += solve($n-1, $x-$i);
}
$f[$n][$x] = $total;
return $total;
}
print solve(10, 70), "\n";
# 2018464261
@mjdominus
Copy link
Author

The original poster specified that the order of the summands does matter, so that 1+3 and 3+1 would be considered two different ways to sum two numbers to make a total of 4.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment