Discussion on: Daily Challenge #14 - Square into Squares

[E. Choroba]

Perl solution, using recursion:

#!/usr/bin/perl
use warnings;
use strict;

sub _decompose {
    my ($n, $target, $decomposition, $sum) = @_;

    return $decomposition if $target == $sum;

    my $smaller = int sqrt $n - 1;
    while ($smaller) {
        my $small_square = $smaller ** 2;
        if ($sum + $small_square <= $target) {
            my $d = _decompose(
                $smaller ** 2, $target,
                [ $smaller, @$decomposition ], $sum + $smaller ** 2
            );
            return $d if @$d;
        }
        --$smaller;
    }
    return []
}

sub decompose {
    my ($n) = @_;
    my $square = $n ** 2;
    return _decompose($square, $square, [], 0)
}

use Test::More tests => 2;
is_deeply decompose(11), [1, 2, 4, 10], 'eleven';
is_deeply decompose(12), [1, 2, 3, 7, 9], 'twelve';

I added 12 as a test, too, because for 12, 11 is not part of its decomposition.