Count the coins/0-1

Count the coins/0-1 is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

Let say you have some coins in your wallet and you want to have a given sum.

You can use each coin zero or one time.

How many ways can you do it ?

The result should be a number.

For instance the answer is 10 when coins = [1, 2, 3, 4, 5] and sum = 6.

Task

Show the result the for the following examples:

•   coins = [1, 2, 3, 4, 5] and sum = 6

•   coins = [1, 1, 2, 3, 3, 4, 5] and sum = 6

•   coins = [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] and sum = 40

Extra

•   Show the result of the same examples when the order you take the coins doesn't matter.

•   Show an example of coins you used to reach the given sum by giving the indices of coins you have taken.

Perl

<lang perl>#!/usr/bin/perl

use strict; # https://rosettacode.org/wiki/Count_the_coins/0-1 use warnings;

countcoins( 6, [1, 2, 3, 4, 5] ); countcoins( 6, [1, 1, 2, 3, 3, 4, 5] );

1. countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );

sub countcoins

 {
 my ($want, $coins) = @_;
 print "\nsum $want coins @$coins\n";
 count($want, [], 0, $coins);
 }

sub count

 {
 my ($want, $used, $sum, $have) = @_;
 if( $sum == $want ) { print "used @$used\n" }
 elsif( $sum > $want or @$have == 0 ) {}
 else
   {
   my ($thiscoin, @rest) = @$have;
   count( $want, [@$used, $thiscoin], $sum + $thiscoin, \@rest);
   count( $want, $used, $sum, \@rest);
   }
 }</lang>

Third case not shown because it's too large.

Output:

sum 6 coins 1 2 3 4 5
used 1 2 3
used 1 5
used 2 4

sum 6 coins 1 1 2 3 3 4 5
used 1 1 4
used 1 2 3
used 1 2 3
used 1 5
used 1 2 3
used 1 2 3
used 1 5
used 2 4
used 3 3