We're a place where coders share, stay up-to-date and grow their careers.
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.
Perl solution, using recursion:
I added 12 as a test, too, because for 12, 11 is not part of its decomposition.