Count the coins/0-1

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.

Go

Translation of: Wren

<lang go>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)

}</lang>

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:<lang J>selcoins=: {{ #:I.x=(#:i.2^#y)+/ .*y }} ccoins=: Template:(</lang>

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:<lang J> 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</lang>

Some example coin selections:<lang J> 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</lang>

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: <lang jq>

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 ;

</lang> <lang jq>

1. 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; </lang>

The task <lang jq> 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</lang>

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

<lang 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)

</lang>

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

<lang Mathematica>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[selAll, 2] == sum,
     Sow@<|"Coins" -> selAll, 2, 
       "Indices" -> selAll, 1|>
     ]
    ,
    {i, 0, max}
    ];
 out = out2, 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]] &</lang>

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

<lang MiniZinc> %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; </lang>

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

<lang MiniZinc> %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; </lang>

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

<lang MiniZinc> %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; </lang>

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. <lang Nim>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)</lang>

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'. <lang pascal>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. </lang>

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

<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

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

<lang 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()</lang>

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.

<lang perl6>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"

}</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

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. <lang ecmascript>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)</lang>

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)