I've just been reading MJD's Higher Order Perl, which gives the development for the similar "sums to exactly X" problem (but I don't have the book with me to quote directly).

Alternatively, there's Algorithm::Knapsack, but it claims it's brute force, and doesn't handle complex data structures.

Perhaps following the lead of HOP wrt callbacks, you can convert A::K to something more generally useful?

Update: HOP gives this solution for the exact partition problem (p 206):

# Usage: @list = partition( $some_target, \@list );

sub partition {
  my ($target, $treasures) = @_;
  return [] if $target == 0;
  return () if $target < 0 || @$treasures == 0;

  my ($first, @rest) = @$treasures;
  my @solutions = partition($target-$first, \@rest);
  return ((map{[$first,@$_]} @solutions),
         partition($target, \@rest));
}
[download]

MJD goes on to improve on this in various ways, but that should suit you for now :)

(Unfortunately, the HOP examples website isn't up yet, so I had to type this in by hand, and it's untested.)