#!/usr/bin/env perl

# depth-first search on a tree of combinations
# aim is to use @input numbers to make the target sum.
# by bliako
# for https://perlmonks.org/?node_id=11102502
# 08/07/2019

use strict;
use warnings;

# from https://github.com/hadjiprocopis/Tree-Nary-Tiny
# or any other nary-tree implementation, e.g.
# https://metacpan.org/pod/Tree::Simple
use Tree::Nary::Tiny;

#for deep recursion try this:
#my @input = map { 2+int(rand(20)) } 0..100;
#my $target = 15783;

my @input = qw/ 2 5 7 /;
my $target = 15;

my $T = Tree::Nary::Tiny->new(
	undef, # parent
	"root",
	undef, # data
	sub { return $_[0] }
);
my @solutions;
find($T, \@input, $target, \@solutions);

print "$0 : here are all the solutions:\n";
my $i = 1;
foreach (@solutions){
	my $sum = 0;
	$sum += $_ foreach (@$_);
	if( $sum != $target ){ die "wrong solution, this should not be happening." }
	print $i . ")". join(",", @$_)."\n";
	$i++;
}

sub	find {
	my $n = $_[0];
	my $input = $_[1];
	my $target = $_[2];
	my $solutions = $_[3];
	my $v = $n->value();

	if( defined $v && $v->{'sum'} == $target ){
		my @asol = ();
		while( defined $n->parent() ){
			push @asol, $n->value()->{'number'};
			$n = $n->parent();
		}
		push @$solutions, \@asol;
		print "found solution: ".join(",",@asol)."\n";
		return
	}

	my $sum = defined($v) ? $v->{'sum'} : 0;
	foreach(@$input){
                # added this to make sure that we have combinations rather than permutations:
                # see haukex's comment below
                next if( defined($v) && $_ < $v->{'number'} );
		if( $sum + $_ <= $target ){
			my $nn = Tree::Nary::Tiny->new(
				$n, # parent
				$_, # an id, nothing important
				{
					'sum' => $sum + $_,
					'number' => $_
				}, # the data to hold
			);
			find($nn, $input, $target, $solutions);
		}
	}
}

##</code><code>##

tr.pl : here are all the solutions:
1)5,2,2,2,2,2
2)2,5,2,2,2,2
3)7,2,2,2,2
4)2,2,5,2,2,2
5)2,7,2,2,2
6)2,2,2,5,2,2
7)2,2,7,2,2
8)2,2,2,2,5,2
9)2,2,2,7,2
10)2,2,2,2,2,5
11)5,5,5
12)2,2,2,2,7

##</code><code>##

        foreach(@$input){
                # added this to make sure that we have combinations rather than permutations:
                # see haukex's comment below
                next if( defined($v) && $_ < $v->{'number'} );
                ...