Download the raw code.

#!/usr/bin/env perl6
# This is perl6 version 2011.12-18-ga7fd89e built on parrot 3.11.0 revision RELEASE_3_11_0

my @ANS of Int;
my Int $TARGET;

sub solve( @nums ) {
    if 0 < @ANS.elems <= @nums.elems {
        # Do nothing. We already have a better solution.
    elsif @nums[*-1] < $TARGET {
        # Try adding the largest numbers first so that the first
        # solution will have approximately log $TARGET elements.
        for @nums.reverse -> $k {
            @nums.push( @nums[*-1] + $k );
            solve( @nums );
    elsif @nums[*-1] == $TARGET {
        @ANS = @nums;

sub MAIN {
    for lines() {
        $TARGET = $_.Int;
        @ANS = ();

        my @nums of Int = 1; # The only array needed for all calculations.
        solve( @nums );

        printf "(%s)\n", @ANS.sort.join( ", " );

# The C++ equivalent allocates approximately 10 kb of memory.
# Rakudo burns hundreds of megabytes, and it gets much worse
# for multi-line input. (memory leak?)


The code produces correct results.


Why is an array meant to contain integers called @nums? :-)

Clarity of intent

The code is very clear and easy to read and understand in its entirety.

The sentence fragment @nums[*-1] keeps showing up — would maybe have been better to shove it into a variable near the start of &solve?

Currently no implementation supports the syntax my @nums of Int except Rakudo, and it ignores the type trait — so using it provides documentation but no type checking.

Algorithmic efficiency

There is nothing especially fast or slow about this solution. It recursively tries all possible chains.

Idiomatic use of Perl 6

Nice chained operators.

There's nothing wrong with writing it my @nums of Int, even though the form my Int @nums is more commonly seen. (It should be noted that both ways of writing it have weaknesses in Rakudo when it comes to typechecking. The my @nums of Int happens to have one more weakness: you can assign non-Ints to individual elements. You can't with my Int @nums.)


This program is short without being compact.