P is for Practical PerlMonks

### Re: Find combination of numbers whose sum equals X

by LanX (Cardinal)
 on Nov 22, 2020 at 00:35 UTC Need Help??

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

Create A New User
Node Status?
node history
Node Type: note [id://11123998]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?