Coin Change — Counting Ways

Counting coin representations has two distinct meanings: unordered combinations of denomination counts, or ordered sequences of individual coin choices. Both are valid questions and need different loop orders. We compute both modulo a prime on the same input, making their state invariants visible rather than treating loop order as a memorized trick.

Prerequisites: Coin Change Minimum; modular arithmetic; layered counting.

Build the idea

1. Recognize the repeated subproblems

   Enumerating coin sequences repeats suffix amounts and may also count many permutations of the same multiset. Before designing DP, ask whether 1+3 and 3+1 are different outcomes. Constraints with moderate target A permit O(nA) work, but the intended combinatorial object determines whether denomination type or final position should define disjoint cases.

2. Define the state

   combinations[x], after an outer prefix of coin types, counts multisets totaling x using only those types. ordered[x] counts sequences totaling x using any denomination. Deduplicate equal denomination values because input duplicates represent the same unlimited type. Treating duplicate values as separate types would inflate combination counts without representing new choices.

3. Derive the transition

   For combinations, take coin c as the outer loop and scan x upward: adding one c to combinations[x−c] stays in the current type layer, allowing repeats but never later placing an earlier type after a later one. For ordered sequences, take amount x as the outer loop and sum ordered[x−c] over possible final coins. Different final coins/preceding sequences are disjoint ordered outcomes.

   $$\mathrm{ordered}\left[x\right]=\Sigma \mathrm{ordered}[x-c]$$

4. Base cases and computation order

   Both arrays start with value one at amount zero, denoting the single empty representation; all other counts start at zero. Combination type order is arbitrary but fixed; ascending sums permit unlimited copies. Ordered recurrence uses smaller amounts because c>0. Reduce additions modulo 10^9+7 to keep counts bounded; modular zero does not imply the underlying exact count is zero.

5. Correctness and invariant

   Type-layer induction partitions combinations by the number of copies of the newest coin and produces each multiset once. Final-coin induction partitions ordered sequences by their last entry and counts each sequence once. Exchanging the loops changes the counted object, not just performance. A minimum-coin recurrence would use min instead of either sum and would not answer either counting question.

6. Work the example

   For coins {1,2,3} and amount 4, combinations are 1+1+1+1,1+1+2,2+2,1+3: four. Ordered sequences additionally distinguish permutations of 1,1,2 and of 1,3, giving seven. The table compares the count arrays across amounts 0…4; both agree at zero on the empty representation.

   amount	0	1	2	3	4
   combinations	1	1	2	3	4
   ordered sequences	1	1	2	4	7

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<vector>
#include<algorithm>
int main(){
    int n,A;
    std::cin>>n>>A;
    std::vector<int>coins(n);
    for(int&c:coins){
        std::cin>>c;
    }
    std::sort(coins.begin(),coins.end());
    coins.erase(std::unique(coins.begin(),coins.end()),coins.end());
    const long long MOD=1000000007;
    std::vector<long long>combinations(A+1),ordered(A+1);
    combinations[0]=ordered[0]=1;
    for(int c:coins){
        for(int x=c;x<=A;++x){
            combinations[x]=(combinations[x]+combinations[x-c])%
                MOD; // Coin types form the outer layer: no order double-counting.
        }
    }
    for(int x=1;x<=A;++x){
        for(int c:coins){
            if(c<=x){
                ordered[x]=(ordered[x]+ordered[x-c])%MOD;
            }
        }
    }
    std::cout<<combinations[A]<<' '<<ordered[A]<<'\n';
}

Complexity analysis

Two O(nA) dynamic programs plus O(n log n) sorting/deduplication; O(A+n) storage. Conceptual combination states have type and amount dimensions, compressed in-place. Each modular addition is performed in long long before reduction.

Example input and output

Read n A (1≤n≤100,0≤A≤100000), then positive denominations≤10^6, unlimited copies; duplicate values are deduplicated. Print unordered combination count and ordered sequence count modulo 10^9+7.

Input

3 4
1 2 3

Output

4 7

For coins {1,2,3} and amount 4, combinations are 1+1+1+1,1+1+2,2+2,1+3: four. Ordered sequences additionally distinguish permutations of 1,1,2 and of 1,3, giving seven. The table compares the count arrays across amounts 0…4; both agree at zero on the empty representation.

Practical applications

Use type-layer counting for multisets and final-action counting for sequences. The same distinction appears in dice sums, compositions, unbounded selections and ordered construction. Different restrictions can require extra state to prevent double-counting.

Check your understanding

Which loop structure counts ordered sequences in the shown recurrence?

Put it into practice

List every representation of amount five with coins 1 and 2.