arrays - 给定一个数字列表，找到一个子集，该子集与一个数字范围内的任何数字相加

Question

当给定一个由正整数或负整数组成的数组和一个值 k 以使该数组中的某些数字总和为从 1 到 k 的任何数字时，我该如何创建一个返回 true 或 false 的方法。

例如，给定一个数组 [-10,20,14,-3] 和 k=6，这将返回 true 为 14+(-10) = 4，它介于 1 和 6 之间。

我知道这需要动态编程（因为它必须在多项式时间内运行），但我不确定如何实现它，所以任何帮助都会很棒。

谢谢！

Answer 1

我认为方法是对数字进行排序，然后将一个越来越小的列表相加，直到它起作用

这是scala中的答案

def sumit(x : List[Int], k: Int ): List[Int] = x match { case x  => if(x.sum > k ) x else sumit(x.init, k)

The List must be presorted, ie call like this
val numbers=List(-9, 1, 3, 6, 5, 1, 2)
sumit( numbers.sorted.reverse, 16)   

在 perl 中

#!/usr/bin/perl
#



sub any_adds_to {
    my $target=shift;
    my $list=shift;
    my @sorted=sort {$a <=> $b} @$list;
    my $v=0;
    for (@sorted) {
        $v=$v+$_;
        last if $v>$target;
    }
    return $v>$target;
}

sub assert {
        $_[0] ? "OK\n" : "FAIL\n";
}

my %test_as_false=(18=>[3,2,4,2,6],
          255=>[32,33,34,35,35],
          1200=>[-1,1000,1,199]);
for my $val_to_find (keys %test_as_false) {
    print assert(not(any_adds_to($val_to_find, $test_as_false{$val_to_find})));
}

my %test_as_correct=(18,[2,4,6,8],
                     255,[65,66,67,68],
                     1200=>[1,1000,1,199]);

for my $val_to_find (keys %test_as_correct) {
    print assert((any_adds_to($val_to_find, $test_as_correct{$val_to_find})));
}