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. For instance the answer is 3 when coins = [1, 2, 3, 4, 5] and sum = 6.

•   Show an example of coins you used to reach the given sum and their indices. See Perl for this case.

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] ); countcoins( 40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] );

my $count;

sub countcoins

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

sub count

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

Output:

sum 6 coins 1 2 3 4 5
Number of ways: 3

sum 6 coins 1 1 2 3 3 4 5
Number of ways: 9

sum 40 coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
Number of ways: 464

Raku

This is pretty much duplicating other tasks, in process if not wording. First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations. Even though I am adding a solution, my vote would be for deletion as it doesn't really add anything to the other tasks; Combinations, Permutations, Subset sum problem and to a large extent 4-rings or 4-squares puzzle.

<lang perl6>sub which (*@items, :$sum-to) { ^@items .combinations.grep: { @items[$_].sum == $sum-to } }

for <1 2 3 4 5>, 6

  ,<1 1 2 3 3 4 5>, 6
  ,<1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100>, 40
 -> @items, $sum {

   put "\n\nHow many combinations of [{ @items.join: ', ' }] sum to $sum?";

   given @items.&which: :sum-to( $sum ) {
       put "\nOrder unimportant:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' );
       put .pick(10).sort».join(', ').join: "\n";
   }

   given @items.&which( :sum-to( $sum ) ).map: { Slip(.permutations) } {
       put "\nOrder important:\nCount: { +$_ }\nIndices" ~ ( +$_ > 10 ?? ' (10 random examples):' !! ':' );
       put .pick(10).sort».join(', ').join: "\n";
   }

}</lang>

Output:

How many combinations of [1, 2, 3, 4, 5] sum to 6?

Order unimportant:
Count: 3
Indices:
0, 1, 2
0, 4
1, 3

Order important:
Count: 10
Indices:
0, 1, 2
0, 2, 1
0, 4
1, 0, 2
1, 2, 0
1, 3
2, 0, 1
2, 1, 0
3, 1
4, 0


How many combinations of [1, 1, 2, 3, 3, 4, 5] sum to 6?

Order unimportant:
Count: 9
Indices:
0, 1, 5
0, 2, 3
0, 2, 4
0, 6
1, 2, 3
1, 2, 4
1, 6
2, 5
3, 4

Order important:
Count: 38
Indices (10 random examples):
0, 4, 2
1, 2, 3
1, 2, 4
1, 5, 0
1, 6
2, 1, 3
2, 1, 4
2, 4, 0
3, 2, 0
6, 0


How many combinations of [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100] sum to 40?

Order unimportant:
Count: 464
Indices (10 random examples):
0, 1, 2, 3, 5, 7, 10, 11
0, 1, 2, 3, 5, 8, 12
0, 1, 2, 3, 6, 7, 11, 13
0, 3, 5, 7, 9, 13
0, 3, 9, 10, 11
1, 2, 5, 7, 9, 13
4, 5, 10, 12, 13
5, 6, 7, 9, 10
5, 6, 10, 11, 12
5, 8, 10, 12

Order important:
Count: 3782932
Indices (10 random examples):
0, 11, 3, 4, 7, 5, 6, 1, 2
1, 10, 5, 4, 6, 2, 0, 3, 7
2, 7, 13, 4, 1, 3, 5, 6, 0
2, 12, 4, 13, 10, 1
3, 0, 5, 4, 7, 13, 6, 2, 1
5, 7, 9, 4, 0, 1, 2, 3
6, 2, 7, 11, 0, 3, 5, 1, 4
10, 0, 12, 6, 5, 3, 4
13, 0, 1, 5, 7, 3, 2, 12
13, 6, 10, 1, 4, 3, 2, 0