Count the coins/0-1: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:37, 21 November 2023

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 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 Raku for this case.

11l

Translation of: Nim

T Solver
   Int want, width
   count1 = 0
   count2 = 0

   F (want, width)
      .want = want
      .width = width

   F count(Int sum; [Int] used, have, uindices, rindices) -> N
      I sum == .want
         .count1++
         .count2 += factorial(used.len)
         I .count1 < 11
            V uindiceStr = uindices.join(‘ ’).ljust(.width)
            print(‘  indices ’uindiceStr‘  =>  used ’used.join(‘ ’))
      E I sum < .want & !have.empty
         V thisCoin = have[0]
         V index = rindices[0]
         V rest = have[1..]
         V new_rindices = rindices[1..]
         .count(sum + thisCoin, used [+] thisCoin, rest, uindices [+] index, new_rindices)
         .count(sum, used, rest, uindices, new_rindices)

F count_coins(Int want, [Int] &coins, Int width)
   print(‘Sum ’want‘ from coins ’coins.join(‘ ’))
   V solver = Solver(want, width)
   V rindices = Array(0 .< coins.len)
   solver.count(0, [Int](), coins, [Int](), rindices)
   I solver.count1 > 10
      print(‘  .......’)
      print(‘  (only the first 10 ways generated are shown)’)
   print(‘Number of ways - order unimportant : ’(solver.count1)‘ (as above)’)
   print(‘Number of ways - order important   : ’(solver.count2)" (all perms of above indices)\n")

count_coins(6, &[1, 2, 3, 4, 5], 5)
count_coins(6, &[1, 1, 2, 3, 3, 4, 5], 7)
count_coins(40, &[1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)

Output:

Sum 6 from coins 1 2 3 4 5
  indices 0 1 2  =>  used 1 2 3
  indices 0 4    =>  used 1 5
  indices 1 3    =>  used 2 4
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins 1 1 2 3 3 4 5
  indices 0 1 5    =>  used 1 1 4
  indices 0 2 3    =>  used 1 2 3
  indices 0 2 4    =>  used 1 2 3
  indices 0 6      =>  used 1 5
  indices 1 2 3    =>  used 1 2 3
  indices 1 2 4    =>  used 1 2 3
  indices 1 6      =>  used 1 5
  indices 2 5      =>  used 2 4
  indices 3 4      =>  used 3 3
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
  indices 0 1 2 3 4 5 6 7 10  =>  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 11  =>  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 12  =>  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 13  =>  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 8     =>  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 6 9     =>  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 8     =>  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 9     =>  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 10 11   =>  used 1 2 3 4 5 5 10 10
  indices 0 1 2 3 4 5 10 12   =>  used 1 2 3 4 5 5 10 10
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)

ALGOL 68

Translation of: Go

which is

Translation of: Wren

BEGIN # count the ways of summing coins to a particular number - translation of the Go sample #
    INT countu := 0;  # order unimportant     #
    INT counti := 0;  # order important       #
    INT width  := 0;  # for printing purposes #

    PROC factorial = (INT n )INT:
         BEGIN
            INT prod := 1;
            FOR i FROM 2 TO n DO
                prod *:= i
            OD;
            prod
         END # factorial # ;

    OP LEN = ( []INT  a )INT: ( UPB a - LWB a ) + 1;
    OP LEN = ( STRING a )INT: ( UPB a - LWB a ) + 1;
    PROC append = ( []INT a, INT b )[]INT:
         BEGIN
            [ 1 : LEN a + 1 ]INT result;
            result[ 1 : LEN a ] := a;
            result[ LEN a + 1 ] := b;
            result
         END # append # ;
    OP TOSTRING = ( []INT a )STRING:
       BEGIN
            STRING result    := "[";
            STRING separator := "";
            FOR i FROM LWB a TO UPB a DO
                result +:= separator + whole( a[ i ], 0 );
                separator := " "
            OD;
            result +:= "]"
       END # TOSTRING # ;
    PROC pad = ( STRING a, INT width )STRING:
         IF INT len a = LEN a; len a >= width THEN a ELSE a + ( " " * ( width - len a ) ) FI;
             
    PROC count = ( INT want, []INT used, INT sum, []INT have, uindices, rindices )VOID:
         IF sum = want THEN
            countu +:= 1;
            counti +:= factorial( LEN used );
            IF countu < 11 THEN
                STRING uindices str = TOSTRING uindices;
                print( ( "  indices ", pad( uindices str, width ), " => used ", TOSTRING used, newline ) )
            FI
         ELIF sum < want AND LEN have /= 0 THEN
            INT this coin = have[ LWB have ];
            INT index     = rindices[ LWB rindices ];
            []INT rest    = have[ LWB have + 1 : ];
            count( want, append( used, this coin ), sum + this coin, rest,
                   append( uindices, index ), rindices[ LWB rindices + 1 : ] );
            count( want, used, sum, rest, uindices, rindices[ LWB rindices + 1 : ] )
         FI # count # ;

    PROC count coins = ( INT want, []INT coins, INT rqd width )VOID:
         BEGIN
            print( ( "Sum ", whole( want, 0 ), " from coins ", TOSTRING coins, newline ) );
            countu := 0;
            counti := 0;
            width  := rqd width;
            [ 0 : LEN coins - 1 ]INT rindices;
            FOR i FROM LWB rindices TO UPB rindices DO
                rindices[ i ] := i
            OD;
            count( want, []INT(), 0, coins, []INT(), rindices );
            IF countu > 10 THEN
                print( ( "  .......", newline ) );
                print( ( "  (only the first 10 ways generated are shown)", newline ) )
            FI;
            print( ( "Number of ways - order unimportant : ", whole( countu,  0 )
                   , " (as above)", newline ) );
            print( ( "Number of ways - order important   : ", whole( counti, 0 )
                   , " (all perms of above indices)", newline, newline ) )
         END # count coins # ;

    BEGIN # task #
        count coins(  6, ( 1, 2, 3, 4, 5 ), 7 );
        count coins(  6, ( 1, 1, 2, 3, 3, 4, 5 ), 9 );
        count coins( 40, ( 1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100 ), 20 )
    END
END

Output:

Sum 6 from coins [1 2 3 4 5]
  indices [0 1 2] => used [1 2 3]
  indices [0 4]   => used [1 5]
  indices [1 3]   => used [2 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins [1 1 2 3 3 4 5]
  indices [0 1 5]   => used [1 1 4]
  indices [0 2 3]   => used [1 2 3]
  indices [0 2 4]   => used [1 2 3]
  indices [0 6]     => used [1 5]
  indices [1 2 3]   => used [1 2 3]
  indices [1 2 4]   => used [1 2 3]
  indices [1 6]     => used [1 5]
  indices [2 5]     => used [2 4]
  indices [3 4]     => used [3 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100]
  indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 6 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 10 11]  => used [1 2 3 4 5 5 10 10]
  indices [0 1 2 3 4 5 10 12]  => used [1 2 3 4 5 5 10 10]
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)

FreeBASIC

Based on the Phix entry and the Nim entry

#define factorial(n)  Iif(n<2, 1, n*factorial1(n-1))

REM silly way
Function silly(coins() As Short, tgt As Short, cdx As Short = 1) As Integer
    Dim As Integer count = 0
    If tgt = 0 Then
        count += 1
    Elseif tgt > 0 And cdx <= Ubound(coins) Then
        count += silly(coins(), tgt-coins(cdx), cdx+1)
        count += silly(coins(), tgt, cdx+1)
    End If
    Return count
End Function

REM very silly way
Function very_silly(coins() As Short, tgt As Short, cdx As Short = 1, taken As Short = 0) As Integer
    Dim As Integer count = 0
    If tgt = 0 Then
        count += factorial(taken)
    Elseif tgt > 0 And cdx <= Ubound(coins) Then
        count += very_silly(coins(), tgt-coins(cdx), cdx+1, taken+1)
        count += very_silly(coins(), tgt, cdx+1, taken)
    End If
    Return count
End Function

Sub countCoins(coins() As Short, tgt As Short)
    Print "Sum"; tgt; " from coins "; 
    For a As Short = 1 To Ubound(coins)
        Print coins(a);
    Next a
    Print !"\nNumber of ways - order unimportant:"; silly(coins(), tgt)
    Print "Number of ways - order important  :"; very_silly(coins(), tgt); !"\n"
End Sub

Dim As Short test0(1 To ...) = {1, 2, 3, 4, 5}
countCoins(test0(), 6)

Dim As Short test1(1 To ...) = {1, 1, 2, 3, 3, 4, 5}
countCoins(test1(), 6)

Dim As Short test2(1 To ...) = {1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100}
countCoins(test2(), 40)

Sleep

Output:

Sum 6 from coins  1 2 3 4 5
Number of ways - order unimportant: 3
Number of ways - order important  : 10

Sum 6 from coins  1 1 2 3 3 4 5
Number of ways - order unimportant: 9
Number of ways - order important  : 38

Sum 40 from coins  1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
Number of ways - order unimportant: 464
Number of ways - order important  : 3782932

Go

Translation of: Wren

package main

import "fmt"

var cnt = 0  // order unimportant
var cnt2 = 0 // order important
var wdth = 0 // for printing purposes

func factorial(n int) int {
    prod := 1
    for i := 2; i <= n; i++ {
        prod *= i
    }
    return prod
}

func count(want int, used []int, sum int, have, uindices, rindices []int) {
    if sum == want {
        cnt++
        cnt2 += factorial(len(used))
        if cnt < 11 {
            uindicesStr := fmt.Sprintf("%v", uindices)
            fmt.Printf("  indices %*s => used %v\n", wdth, uindicesStr, used)
        }
    } else if sum < want && len(have) != 0 {
        thisCoin := have[0]
        index := rindices[0]
        rest := have[1:]
        rindices := rindices[1:]
        count(want, append(used, thisCoin), sum+thisCoin, rest,
            append(uindices, index), rindices)
        count(want, used, sum, rest, uindices, rindices)
    }
}

func countCoins(want int, coins []int, width int) {
    fmt.Printf("Sum %d from coins %v\n", want, coins)
    cnt = 0
    cnt2 = 0
    wdth = -width
    rindices := make([]int, len(coins))
    for i := range rindices {
        rindices[i] = i
    }
    count(want, []int{}, 0, coins, []int{}, rindices)
    if cnt > 10 {
        fmt.Println("  .......")
        fmt.Println("  (only the first 10 ways generated are shown)")
    }
    fmt.Println("Number of ways - order unimportant :", cnt, "(as above)")
    fmt.Println("Number of ways - order important   :", cnt2, "(all perms of above indices)\n")
}

func main() {
    countCoins(6, []int{1, 2, 3, 4, 5}, 7)
    countCoins(6, []int{1, 1, 2, 3, 3, 4, 5}, 9)
    countCoins(40, []int{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 20)
}

Output:

Sum 6 from coins [1 2 3 4 5]
  indices [0 1 2] => used [1 2 3]
  indices [0 4]   => used [1 5]
  indices [1 3]   => used [2 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins [1 1 2 3 3 4 5]
  indices [0 1 5]   => used [1 1 4]
  indices [0 2 3]   => used [1 2 3]
  indices [0 2 4]   => used [1 2 3]
  indices [0 6]     => used [1 5]
  indices [1 2 3]   => used [1 2 3]
  indices [1 2 4]   => used [1 2 3]
  indices [1 6]     => used [1 5]
  indices [2 5]     => used [2 4]
  indices [3 4]     => used [3 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins [1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100]
  indices [0 1 2 3 4 5 6 7 10] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 11] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 12] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 7 13] => used [1 2 3 4 5 5 5 5 10]
  indices [0 1 2 3 4 5 6 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 6 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 8]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 7 9]    => used [1 2 3 4 5 5 5 15]
  indices [0 1 2 3 4 5 10 11]  => used [1 2 3 4 5 5 10 10]
  indices [0 1 2 3 4 5 10 12]  => used [1 2 3 4 5 5 10 10]
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)

J

Implementation:

selcoins=: {{ #:I.x=(#:i.2^#y)+/ .*y }}
ccoins=: {{ (#i), +/!x:+/"1 i=. x selcoins y }}

selcoins identifies the valid selections of the coins. ccoins counts them, giving two counts (first is where coin order does not matter, second is where each permutation of physical coins is counted separately).

Task examples:

   6 ccoins 1 2 3 4 5
3 10
   6 ccoins 1 1 2 3 3 4 5
9 38
   40 ccoins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
464 3782932

Some example coin selections:

   rplc&(' 0';'')"1":6 (]#~selcoins) 1 2 3 4 5
2 4  
1 5  
1 2 3
   rplc&(' 0';'')"1":6 (]#~selcoins) 1 1 2 3 3 4 5
3 3  
2 4  
1 5  
1 2 3
1 2 3
1 5  
1 2 3
1 2 3
1 1 4
   rplc&(' 0';'')"1":40 (]#~9{.selcoins) 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
10 10 10 10
15 25      
15 25      
15 15 10   
15 15 10   
15 15 10   
15 15 10   
 5 10 25   
 5 10 25

jq

Works with: jq

Works with gojq, the Go implementation of jq

The solutions presented in this section use generic `combinations` and `permutations` functions defined as follows:

# Input: an array of arrays
# Output: a stream of arrays corresponding to the selection of exactly one item
# from each top-level array
def combinations:
  if length == 0 then []
  else
  .[0][] as $x
  | (.[1:] | combinations) as $y
  | [$x] +  $y
  end ;

# Generate a stream of all the permutations of the input array
def permutations:
  if length == 0 then []
  else
    range(0;length) as $i
    | [.[$i]] + (del(.[$i])|permutations)
  end ;

## Generic helper functions:
def count(s): reduce s as $x (0; .+1);

# Input: an array [a, b, ... ]
# Output: [ [a,0], [b,0],... ] | combinations
def zero_or_one: [ .[] | [., 0] ] | combinations;

The task

def count_combinations_with_sum($sum):
  count( zero_or_one | select(add == $sum));

def count_permutations_with_sum($sum):
  count( zero_or_one | select(add == $sum) | map(select(.!=0)) | permutations);

# Each task takes the form of [ARRAY, SUM]
def task:
  . as [$array, $sum]
  | $array
  | count_combinations_with_sum($sum) as $n
  | count_permutations_with_sum($sum) as $p
  | "With coins \($array) and target sum \($sum):",
    "   #combinations is \($n)",
    "   #permutations is \($p)\n";

[[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]
| task

Output:

With coins [1,2,3,4,5] and target sum 6:
   #combinations is 3
   #permutations is 10

With coins [1,1,2,3,3,4,5] and target sum 6:
   #combinations is 9
   #permutations is 38

With coins [1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100] and target sum 40:
   #combinations is 464
   #permutations is 3782932

Julia

using Combinatorics

function coinsum(coins, targetsum; verbose=true)
    println("Coins are $coins, target sum is $targetsum:")
    combos, perms = 0, 0
    for choice in combinations(coins)
        if sum(choice) == targetsum
            combos += 1
            verbose && println("$choice sums to $targetsum")
            for perm in permutations(choice)
                verbose && println("    permutation: $perm")
                perms += 1
            end
        end
    end
    println("$combos combinations, $perms permutations.\n")
end

coinsum([1, 2, 3, 4, 5], 6)
coinsum([1, 1, 2, 3, 3, 4, 5], 6)
coinsum([1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 40, verbose=false)

Output:

Coins are [1, 2, 3, 4, 5], target sum is 6:
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[2, 4] sums to 6
    permutation: [2, 4]
    permutation: [4, 2]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
3 combinations, 10 permutations.

Coins are [1, 1, 2, 3, 3, 4, 5], target sum is 6:
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[1, 5] sums to 6
    permutation: [1, 5]
    permutation: [5, 1]
[2, 4] sums to 6
    permutation: [2, 4]
    permutation: [4, 2]
[3, 3] sums to 6
    permutation: [3, 3]
    permutation: [3, 3]
[1, 1, 4] sums to 6
    permutation: [1, 1, 4]
    permutation: [1, 4, 1]
    permutation: [1, 1, 4]
    permutation: [1, 4, 1]
    permutation: [4, 1, 1]
    permutation: [4, 1, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
[1, 2, 3] sums to 6
    permutation: [1, 2, 3]
    permutation: [1, 3, 2]
    permutation: [2, 1, 3]
    permutation: [2, 3, 1]
    permutation: [3, 1, 2]
    permutation: [3, 2, 1]
9 combinations, 38 permutations.

Coins are [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], target sum is 40:
464 combinations, 3782932 permutations.

Mathematica/Wolfram Language

ClearAll[CoinSums]
CoinSums[coins_List, sum_] := Module[{c, len, max, bin, sel, out},
  c = {Range[Length[coins]], coins} // Transpose;
  c = Select[c, Last /* LessEqualThan[sum]];
  len = Length[c];
  max = 2^len - 1;
  out = Reap@Do[
     bin = IntegerDigits[i, 2, len];
     sel = Pick[c, bin, 1];
     If[Total[sel[[All, 2]]] == sum,
      Sow@<|"Coins" -> sel[[All, 2]], 
        "Indices" -> sel[[All, 1]]|>
      ]
     ,
     {i, 0, max}
     ];
  out = out[[2, 1]];
  Print[Length@out];
  out
  ]
CoinSums[{1, 2, 3, 4, 5}, 6]
CoinSums[{1, 1, 2, 3, 3, 4, 5}, 6]
CoinSums[{1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100}, 40] // Take[#, UpTo[10]] &

Output:

Note that the indexing is 1-based and that for the last case only the first 10 solutions are shown:

3
{<|Coins->{2,4},Indices->{2,4}|>,<|Coins->{1,5},Indices->{1,5}|>,<|Coins->{1,2,3},Indices->{1,2,3}|>}
9
{<|Coins->{3,3},Indices->{4,5}|>,<|Coins->{2,4},Indices->{3,6}|>,<|Coins->{1,5},Indices->{2,7}|>,<|Coins->{1,2,3},Indices->{2,3,5}|>,<|Coins->{1,2,3},Indices->{2,3,4}|>,<|Coins->{1,5},Indices->{1,7}|>,<|Coins->{1,2,3},Indices->{1,3,5}|>,<|Coins->{1,2,3},Indices->{1,3,4}|>,<|Coins->{1,1,4},Indices->{1,2,6}|>}
464
{<|Coins->{10,10,10,10},Indices->{11,12,13,14}|>,<|Coins->{15,25},Indices->{10,15}|>,<|Coins->{15,25},Indices->{9,15}|>,<|Coins->{15,15,10},Indices->{9,10,14}|>,<|Coins->{15,15,10},Indices->{9,10,13}|>,<|Coins->{15,15,10},Indices->{9,10,12}|>,<|Coins->{15,15,10},Indices->{9,10,11}|>,<|Coins->{5,10,25},Indices->{8,14,15}|>,<|Coins->{5,10,25},Indices->{8,13,15}|>,<|Coins->{5,10,25},Indices->{8,12,15}|>}

MiniZinc

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

%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e};
array[Items] of int: weight=[1,2,3,4,5];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;

Output:

selected = {a, b, c};
----------
selected = {a, e};
----------
selected = {b, d};
----------
==========
%%%mzn-stat: initTime=0
%%%mzn-stat: solveTime=0.001
%%%mzn-stat: solutions=3
%%%mzn-stat: variables=21
%%%mzn-stat: propagators=31
%%%mzn-stat: propagations=236
%%%mzn-stat: nodes=11
%%%mzn-stat: failures=3
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=3
%%%mzn-stat-end
Finished in 172msec

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

%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e,f,g};
array[Items] of int: weight=[1,1,2,3,3,4,5];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=6;

Output:

selected = {a, b, f};
----------
selected = {a, c, d};
----------
selected = {a, c, e};
----------
selected = {a, g};
----------
selected = {b, c, d};
----------
selected = {b, c, e};
----------
selected = {b, g};
----------
selected = {c, f};
----------
selected = {d, e};
----------
==========
%%%mzn-stat: initTime=0
%%%mzn-stat: solveTime=0.001
%%%mzn-stat: solutions=9
%%%mzn-stat: variables=29
%%%mzn-stat: propagators=43
%%%mzn-stat: propagations=820
%%%mzn-stat: nodes=35
%%%mzn-stat: failures=9
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=4
%%%mzn-stat-end
Finished in 187msec

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

%Subset sum. Nigel Galloway: January 6th., 2021.
enum Items={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p};
array[Items] of int: weight=[1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100];
var set of Items: selected;
var int: wSelected=sum(n in selected)(weight[n]);
constraint wSelected=40;

Output:

selected = {a, b, c, d, e, f, g, h, k};
----------
selected = {a, b, c, d, e, f, g, h, l};
----------
[ 0 more solutions ]
selected = {a, b, c, d, e, f, g, h, m};
----------
[ 1 more solutions ]
selected = {a, b, c, d, e, f, g, i};
----------
[ 3 more solutions ]
selected = {a, b, c, d, e, f, k, l};
----------
[ 7 more solutions ]
selected = {a, b, c, d, e, g, k, l};
----------
[ 15 more solutions ]
selected = {a, b, c, d, e, j, k};
----------
[ 31 more solutions ]
selected = {a, b, c, d, g, h, l, n};
----------
[ 63 more solutions ]
selected = {a, d, e, h, i, l};
----------
[ 127 more solutions ]
selected = {b, c, e, l, m, n};
----------
[ 206 more solutions ]
selected = {k, l, m, n};
----------
==========
%%%mzn-stat: initTime=0.001
%%%mzn-stat: solveTime=0.011
%%%mzn-stat: solutions=464
%%%mzn-stat: variables=65
%%%mzn-stat: propagators=91
%%%mzn-stat: propagations=122926
%%%mzn-stat: nodes=4203
%%%mzn-stat: failures=1638
%%%mzn-stat: restarts=0
%%%mzn-stat: peakDepth=13
%%%mzn-stat-end
Finished in 207msec

Nim

Translation of: Go

Using a solver object rather than global variables.

import math, sequtils, strutils

type Solver = object
  want: Positive
  count1: Natural
  count2: Natural
  width: Natural

proc count(solver: var Solver; sum: int; used, have, uindices, rindices: seq[int]) =
  if sum == solver.want:
    inc solver.count1
    inc solver.count2, fac(used.len)
    if solver.count1 < 11:
      let uindiceStr = ($uindices.join(" ")).alignLeft(solver.width)
      echo "  indices $1  →  used $2".format(uindiceStr, used.join(" "))
  elif sum < solver.want and have.len != 0:
    let thisCoin = have[0]
    let index = rindices[0]
    let rest = have[1..^1]
    let rindices = rindices[1..^1]
    solver.count(sum + thisCoin, used & thisCoin, rest, uindices & index, rindices)
    solver.count(sum, used, rest, uindices, rindices)

proc countCoins(want: int; coins: openArray[int]; width: int) =
  echo "Sum $# from coins $#".format(want, coins.join(" "))
  var solver = Solver(want: want, width: width)
  var rindices = toSeq(0..coins.high)
  solver.count(0, newSeq[int](), @coins, newSeq[int](), rindices)
  if solver.count1 > 10:
    echo "  ......."
    echo "  (only the first 10 ways generated are shown)"
  echo "Number of ways – order unimportant : ", solver.count1, " (as above)"
  echo "Number of ways – order important   : ", solver.count2, " (all perms of above indices)\n"

when isMainModule:
  countCoins(6, [1, 2, 3, 4, 5], 5)
  countCoins(6, [1, 1, 2, 3, 3, 4, 5], 7)
  countCoins(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 18)

Output:

Sum 6 from coins 1 2 3 4 5
  indices 0 1 2  →  used 1 2 3
  indices 0 4    →  used 1 5
  indices 1 3    →  used 2 4
Number of ways – order unimportant : 3 (as above)
Number of ways – order important   : 10 (all perms of above indices)

Sum 6 from coins 1 1 2 3 3 4 5
  indices 0 1 5    →  used 1 1 4
  indices 0 2 3    →  used 1 2 3
  indices 0 2 4    →  used 1 2 3
  indices 0 6      →  used 1 5
  indices 1 2 3    →  used 1 2 3
  indices 1 2 4    →  used 1 2 3
  indices 1 6      →  used 1 5
  indices 2 5      →  used 2 4
  indices 3 4      →  used 3 3
Number of ways – order unimportant : 9 (as above)
Number of ways – order important   : 38 (all perms of above indices)

Sum 40 from coins 1 2 3 4 5 5 5 5 15 15 10 10 10 10 25 100
  indices 0 1 2 3 4 5 6 7 10  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 11  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 12  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 7 13  →  used 1 2 3 4 5 5 5 5 10
  indices 0 1 2 3 4 5 6 8     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 6 9     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 8     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 7 9     →  used 1 2 3 4 5 5 5 15
  indices 0 1 2 3 4 5 10 11   →  used 1 2 3 4 5 5 10 10
  indices 0 1 2 3 4 5 10 12   →  used 1 2 3 4 5 5 10 10
  .......
  (only the first 10 ways generated are shown)
Number of ways – order unimportant : 464 (as above)
Number of ways – order important   : 3782932 (all perms of above indices)

Pascal

first count all combinations by brute force.Order is important.Modified nQueens.
Next adding weigths by index.
Using Phix wording 'silly'.

program Coins0_1;
{$IFDEF FPC}
   {$MODE DELPHI}
   {$OPTIMIZATION ON,ALL}
{$ELSE}
  {$Apptype console}
{$ENDIF}

uses
  sysutils;// TDatetime
const
  coins1 :array[0..4] of byte = (1, 2, 3, 4, 5);
  coins2 :array[0..6] of byte = (1, 1, 2, 3, 3, 4, 5);
  coins3 :array[0..15] of byte = (1,2,3,4,5,5,5,5,15,15,10,10,10,10,25,100);
  nmax = High(Coins3);
type
{$IFNDEF FPC}
  NativeInt = Int32;
{$ENDIF}
  tFreeCol = array[0..nmax] of Int32;
var
  FreeIdx,
  IdxWeight : tFreeCol;
  n,
  gblCount : nativeUInt;

procedure AddNextWeight(Row,sum:nativeInt);
//order is important
var
  i,Col,Weight : nativeInt;
begin
  IF row <= n then
  begin
    For i := row to n do
    begin
      Col := FreeIdx[i];
      Weight:= IdxWeight[col];
      IF Sum+Weight <= 0 then
      Begin
        Sum +=Weight;
        If Sum = 0 then
        Begin
          Sum -=Weight;
          inc(gblCount);
        end
        else
        begin
          FreeIdx[i] := FreeIdx[Row];
          FreeIdx[Row] := Col;

          AddNextWeight(Row+1,sum);
          //Undo
          Sum -=Weight;
          FreeIdx[Row] := FreeIdx[i];
          FreeIdx[i] := Col;
        end;
      end;
    end;
  end;
end;

procedure CheckBinary(n,MaxIdx,Sum:NativeInt);
//order is not important
Begin
  if sum = 0 then
    inc(gblcount);
  If (sum < 0) AND (n <= MaxIdx) then
  Begin
    //test next sum 
    CheckBinary(n+1,MaxIdx,Sum);// add nothing
    CheckBinary(n+1,MaxIdx,Sum+IdxWeight[n]);//or the actual index
  end;
end;

procedure CheckAll(i,MaxSum:NativeInt);
Begin
  n := i;
  gblCount := 0;
  AddNextWeight(0,-MaxSum);
  Write(MaxSum:6,gblCount:12);
  gblCount := 0;
  CheckBinary(0,i,-MaxSum);
  WriteLn(gblCount:12);
end;

var
  i: nativeInt;

begin
  writeln('sum':6,'very silly':12,'silly':12);
  For i := 0 to High(coins1) do
  Begin
    FreeIdx[i] := i;
    IdxWeight[i] := coins1[i];
  end;
  CheckAll(High(coins1),6);

  For i := 0 to High(coins2) do
  Begin
    FreeIdx[i] := i;
    IdxWeight[i] := coins2[i];
  end;
  CheckAll(High(coins2),6);

  For i := 0 to High(coins3) do
  Begin
    FreeIdx[i] := i;
    IdxWeight[i] := coins3[i];
  end;
  CheckAll(High(coins3),40);
end.

Output:

   sum  very silly       silly
     6          10           3
     6          38           9
    40     3782932         464

// real	0m0,080s ( fpc 3.2.0 -O3 -Xs AMD 2200G 3.7 Ghz )

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);
    }
  }

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

Phix

sane way

In the second test, this counts [1,2,3] as one way to get 6, not counting the other [1,2,3] or the other [1,2,3] or the other [1,2,3].

with javascript_semantics
function choices(sequence coins, integer tgt, cdx=1)
    integer count = 0
    if tgt=0 then
        count += 1
    elsif tgt>0 and cdx<=length(coins) then
        object ci = coins[cdx]
        integer {c,n} = iff(sequence(ci)?ci:{ci,1})
        for j=0 to n do
            count += choices(coins,tgt-j*c,cdx+1)
        end for
    end if
    return count
end function
 
constant tests = {{{1,2,3,4,5},6},
                  {{{1,2},2,{3,2},4,5},6},
                  {{1,2,3,4,{5,4},{15,2},{10,4},25,100},40}}
printf(1,"%V\n",{apply(false,choices,tests)})

Output:

{3,5,33}

silly way

In the second test, this counts [1,2,3] as four ways to get 6, since there are two 1s and two 3s... ("order unimportant")

with javascript_semantics
function silly(sequence coins, integer tgt, cdx=1)
    integer count = 0
    if tgt=0 then
        count += 1
    elsif tgt>0 and cdx<=length(coins) then
        count += silly(coins,tgt-coins[cdx],cdx+1)
        count += silly(coins,tgt,cdx+1)
    end if
    return count
end function
 
constant tests = {{{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}}
printf(1,"%V\n",{apply(false,silly,tests)})

Output:

{3,9,464}

very silly way

In the second test, this counts [1,2,3] as 24 ways to get 6, from 2 1s, 2 3s, and 6 ways to order them ("order important")

with javascript_semantics
function very_silly(sequence coins, integer tgt, cdx=1, taken=0)
    integer count = 0
    if tgt=0 then
        count += factorial(taken)
    elsif tgt>0 and cdx<=length(coins) then
        count += very_silly(coins,tgt-coins[cdx],cdx+1,taken+1)
        count += very_silly(coins,tgt,cdx+1,taken)
    end if
    return count
end function
 
constant tests = {{{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}}
printf(1,"%V\n",{apply(false,very_silly,tests)})

Output:

{10,38,3782932}

Python

from itertools import product, compress

fact = lambda n: n and n*fact(n - 1) or 1
combo_count = lambda total, coins, perm:\
                    sum(perm and fact(len(x)) or 1
                        for x in (list(compress(coins, c))
                                  for c in product(*([(0, 1)]*len(coins))))
                        if sum(x) == total)

cases = [(6,  [1, 2, 3, 4, 5]),
         (6,  [1, 1, 2, 3, 3, 4, 5]),
         (40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100])]

for perm in [False, True]:
    print(f'Order matters: {perm}')
    for s, c in cases:
        print(f'{combo_count(s, c, perm):7d} ways for {s:2d} total from coins {c}')
    print()

Output:

Order matters: False
      3 ways for  6 total from coins [1, 2, 3, 4, 5]
      9 ways for  6 total from coins [1, 1, 2, 3, 3, 4, 5]
    464 ways for 40 total from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100]

Order matters: True
     10 ways for  6 total from coins [1, 2, 3, 4, 5]
     38 ways for  6 total from coins [1, 1, 2, 3, 3, 4, 5]
3782932 ways for 40 total from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100]

Raku

First part is combinations filtered on a certain property. Second part (extra credit) is permutations of those combinations.

This is pretty much duplicating other tasks, in process if not wording. 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.

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 .combinations.grep: { @items[$_].sum == $sum } {
        .&display;
        display .race.map( { Slip(.permutations) } ), '';
    }
}

sub display ($list, $un = 'un') {
    put "\nOrder {$un}important:\nCount: { +$list }\nIndices" ~ ( +$list > 10 ?? ' (10 random examples):' !! ':' );
    put $list.pick(10).sort».join(', ').join: "\n"
}

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

Wren

Translation of: Perl

Well, after some huffing and puffing, the house is still standing so I thought I'd have a go at it. Based on the Perl algorithm but modified to deal with the extra credit.

import "./fmt" for Fmt
import "./math" for Int

var cnt  = 0 // order unimportant
var cnt2 = 0 // order important
var wdth = 0 // for printing purposes

var count // recursive
count = Fn.new { |want, used, sum, have, uindices, rindices|
    if (sum == want) {
        cnt = cnt + 1
        cnt2 = cnt2 + Int.factorial(used.count)
        if (cnt < 11) Fmt.print("  indices $*n => used $n", wdth, uindices, used)
    } else if (sum < want && !have.isEmpty) {
        var thisCoin = have[0]
        var index = rindices[0]
        var rest = have.skip(1).toList
        var rindices = rindices.skip(1).toList
        count.call(want, used + [thisCoin], sum + thisCoin, rest, uindices + [index], rindices)
        count.call(want, used, sum, rest, uindices, rindices)
    }
}

var countCoins = Fn.new { |want, coins, width|
    System.print("Sum %(want) from coins %(coins)")
    cnt  = 0
    cnt2 = 0
    wdth = -width
    count.call(want, [], 0, coins, [], (0...coins.count).toList)
    if (cnt > 10) {
        System.print("  .......")
        System.print("  (only the first 10 ways generated are shown)")
    }
    System.print("Number of ways - order unimportant : %(cnt) (as above)")
    System.print("Number of ways - order important   : %(cnt2) (all perms of above indices)\n")
}

countCoins.call(6, [1, 2, 3, 4, 5], 9)
countCoins.call(6, [1, 1, 2, 3, 3, 4, 5], 9)
countCoins.call(40, [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100], 28)

Output:

Sum 6 from coins [1, 2, 3, 4, 5]
  indices [0, 1, 2] => used [1, 2, 3]
  indices [0, 4]    => used [1, 5]
  indices [1, 3]    => used [2, 4]
Number of ways - order unimportant : 3 (as above)
Number of ways - order important   : 10 (all perms of above indices)

Sum 6 from coins [1, 1, 2, 3, 3, 4, 5]
  indices [0, 1, 5] => used [1, 1, 4]
  indices [0, 2, 3] => used [1, 2, 3]
  indices [0, 2, 4] => used [1, 2, 3]
  indices [0, 6]    => used [1, 5]
  indices [1, 2, 3] => used [1, 2, 3]
  indices [1, 2, 4] => used [1, 2, 3]
  indices [1, 6]    => used [1, 5]
  indices [2, 5]    => used [2, 4]
  indices [3, 4]    => used [3, 3]
Number of ways - order unimportant : 9 (as above)
Number of ways - order important   : 38 (all perms of above indices)

Sum 40 from coins [1, 2, 3, 4, 5, 5, 5, 5, 15, 15, 10, 10, 10, 10, 25, 100]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 10] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 11] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 12] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 7, 13] => used [1, 2, 3, 4, 5, 5, 5, 5, 10]
  indices [0, 1, 2, 3, 4, 5, 6, 8]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 6, 9]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 7, 8]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 7, 9]     => used [1, 2, 3, 4, 5, 5, 5, 15]
  indices [0, 1, 2, 3, 4, 5, 10, 11]   => used [1, 2, 3, 4, 5, 5, 10, 10]
  indices [0, 1, 2, 3, 4, 5, 10, 12]   => used [1, 2, 3, 4, 5, 5, 10, 10]
  .......
  (only the first 10 ways generated are shown)
Number of ways - order unimportant : 464 (as above)
Number of ways - order important   : 3782932 (all perms of above indices)