The only numbers that can be discarded are the ones bigger than the goal number, as any other combination of smaller numbers might sum up to the desired amount.
To find which ones (if any) you will have to check all possible combinations of remaining numbers.
The most simple approach would be to recursively traverse the list, once adding the current number and once leaving it out, pruning the current branch if the sum already exceeds the goal value.
An example (perl) implementation for your problem instance is given in the snippet below:
my @numbers = (4, 5, 10, 10, 23, 67, 889, 150, 50);
my $length = scalar @numbers; # length of the list
sub visit {
my ($i, $sum, $goal, $items) = @_;
# i: current index, sum: sum of numbers currently selected
# goal: goal value to reach, items: list of numbers currently selected
# we found a solution !
print join (", ", @$items) . "\n" if $sum == $goal;
return if $i >= $length || $sum >= $goal;
# continue without adding
visit ($i+1, $sum, $goal, $items);
# continue with adding
visit ($i+1, $sum + $numbers[$i], $goal, [$numbers[$i], @$items]);
}
visit (0, 0, 200, []);
it will report the pair 50, 150
as expected.
Note, that no attempt to remove duplicates was made, so calling with goal value of 77 visit (0, 0, 77, []);
besides the triple 50, 23, 4
the pair 67, 10
will be listed twice, since there are two instances of 10
s there.
Oh, and don't trust any greedy algorithms suggested in other posts, as they are doomed to fail solving knapsack problems.
X
or you want to find if there is a subset whose is ` X`? – Karthik Jul 11 '15 at 4:20