http://www.perlmonks.org?node_id=11123998


in reply to Find combination of numbers whose sum equals X

here another approach, it calculates the possible partial sums in %step with increasing possible $delta.

the solutions are than printed by walking back from $target to zero.

NB: it creates two kind of outputs, a tree with partial solutions and a result hash.

unfortunately this only works efficiently for unique deltas, I'll probably try to fix it tomorrow.

(or better leave it open for the interested reader ;)

use strict; use warnings; use Data::Dump qw/pp dd/; use Data::Dumper; # --- input my @input = (1,99,2,40,50,60,90,3,5,95,100); my $target = 100; my %steps = ( 0 => []); # --- processing my @deltas = sort { $a <=> $b } @input ; for my $delta ( @deltas ) { for my $last (keys %steps) { my $next = $last + $delta; unshift @{$steps{$next}},$last if $next <= $target-$delta # $delta grows! or $next == $target; # goal } # pp $delta, \%steps; } pp \%steps; # --- output my %free; $free{$_}++ for @deltas; our $level = -1; sub walk_back { my ($target,$h_path)=@_; local $level = $level +1; for my $last (@{$steps{$target}}) { my $delta = $target-$last; next unless $free{$delta}; local $free{$delta} = $free{$delta}-1; print "\t" x $level , "+$delta\n"; my $sub_path = $h_path->{$delta} = {}; if ( $last>0 ) { walk_back($last,$sub_path) } else { print "\n\n"; } } } my %path; walk_back($target,\%path); pp \@deltas; print Dumper \%path;

{ "0" => [], "1" => [0], "2" => [0], "3" => [0, 1], "4" => [1], "5" => [0, 2], "6" => [1, 3], "7" => [2], "8" => [3], "9" => [4], "10" => [5], "11" => [6], "40" => [0], "41" => [1], "42" => [2], "43" => [3], "44" => [4], "45" => [5], "46" => [6], "47" => [7], "48" => [8], "49" => [9], "50" => [0, 10], "51" => [11], "100" => [0, 1, 5, 10, 40, 50], } [1, 2, 3, 5, 40, 50, 60, 90, 95, 99, 100] +100 +99 +1 +95 +5 +3 +2 +90 +5 +3 +2 +60 +40 +50 +40 +5 +3 +2 $VAR1 = { '99' => { '1' => {} }, '50' => { '40' => { '5' => { '3' => { '2' => {} } } } }, '95' => { '5' => {}, '3' => { '2' => {} } }, '100' => {}, '60' => { '40' => {} }, '90' => { '5' => { '3' => { '2' => {} } } } };

Cheers Rolf
(addicted to the Perl Programming Language :)
Wikisyntax for the Monastery