微软面试100题(21):求递增数组中和为指定值的子数组

第21题 输入两个整数 n 和 m，从数列1，2，3.......n 中 随意取几个数,
使其和等于 m ,要求将其中所有的可能组合列出来.

这个动态规划应该能做，但是可能比较复杂，如果只是问有几种排列应该还好做，可要列出所有可能性就有点麻烦了。

暂时用回溯算法做了下。用perl实现，代码还比较简单。

大致就是枚举所有可能性。

枚举填入一位result[i] = x，然后在枚举填入下一位 result[i] = y. y的取值范围是（x+1 .. n).

以此类推。

第一个参数是n,第二个参数是m.

my $size = $ARGV[0];
my $target = $ARGV[1];

sub fill{
    my $index = shift;
    my $value = shift;
    my @tresult = @_;
    $tresult[$index] = $value;
    {
        my $sum = 0;
        for(@tresult){
            $sum+=$_;
        }
        if($sum == $target){
            print "@tresult \n";
            return;
        }
        return if($sum> $target);
    }
    for( $value+1 .. $size){
        fill($index+1, $_, @tresult);
    }
}

my @result;
for(1..$size){
    fill(0, $_, @result);
}