t3/az5112-2

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 );
            @nums.pop;
        }
    }
    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.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?)

Same solution as the first one by this author, except with one less call to .sort:

@@ -31,5 +31,5 @@
        solve( @nums );

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

Which makes sense, if you consider that we're always only pushing numbers which are sums of earlier (positive) numbers, so @ANS has to end up sorted already.