#!/usr/bin/perl -w
# 演算法: 用 exhaustive search 解 subset sum
# 作者: 洪朝貴 http://www.cyut.edu.tw/~ckhung
# 授權: public domain (但如果您要將我的程式改寫成有用的大程式,
#	強烈建議將您的版本施以 GPL)
# 執行方式: ./subsetsum -s 17 2 5 9 21
# 表示要從 { 2, 5, 9, 21 } 找出幾個元素, 讓它們的和為 17

use strict;
use Getopt::Std;
use vars qw(%opts @set @picked);

$opts{s} = 0;
getopts('s:', \%opts);
@set = @ARGV;

$#picked = $#set;

sub subsetsum
{
    my ($d, $sum) = @_;

    if ($d > $#set) {
	return $sum == 0;
    }
    $picked[$d] = 0;
    if (subsetsum($d+1, $sum)) {
	return 1;
    }
    $picked[$d] = 1;
    if (subsetsum($d+1, $sum-$set[$d])) {
	return 1;
    }
    return 0;
}

if (subsetsum(0, $opts{s})) {
    for (my $i=0; $i<=$#set; ++$i) {
	print " + $set[$i]" if $picked[$i];
    }
    print " = $opts{s}\n";
} else {
    print "$opts{s} is not the sum of any subset of {";
    foreach (@set) { print " $_"; }
    print " }\n";
}