Re: Find combination of numbers whose sum equals X

[LanX]

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' => {}
                                    }
                           }
                  }
        };