I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

# 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.

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
`package main import "fmt" var cnt = 0  // order unimportantvar cnt2 = 0 // order importantvar 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        index := rindices        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)
```

## 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 arraydef combinations:  if length == 0 then []  else  .[] as \$x  | (.[1:] | combinations) as \$y  | [\$x] +  \$y  end ; # Generate a stream of all the permutations of the input arraydef 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],... ] | combinationsdef zero_or_one: [ .[] | [., 0] ] | combinations; `

` 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 = [email protected][     bin = IntegerDigits[i, 2, len];     sel = Pick[c, bin, 1];     If[Total[sel[[All, 2]]] == sum,      [email protected]<|"Coins" -> sel[[All, 2]],         "Indices" -> sel[[All, 1]]|>      ]     ,     {i, 0, max}     ];  out = out[[2, 1]];  Print[[email protected]];  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] &`
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    let index = rindices    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.
Using Phix wording 'silly'.

`program Coins0_1;{\$IFDEF FPC}   {\$MODE DELPHI}   {\$OPTIMIZATION ON,ALL}{\$ELSE}  {\$Apptype console}{\$ENDIF} uses  sysutils;// TDatetimeconst  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 importantvar  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 importantBegin  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-1use 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}
```

## 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 Fmtimport "/math" for Int var cnt  = 0 // order unimportantvar cnt2 = 0 // order importantvar wdth = 0 // for printing purposes var count // recursivecount = 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        var index = rindices        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)
```