CSES Solutions - Coin Combinations I

Consider a money system consisting of N coins. Each coin has a positive integer value. Your task is to calculate the number of distinct ways you can produce a money sum X using the available coins.

Examples:

Input: N = 3, X = 9, coins[] = {2, 3, 5}
Output: 8
Explanation: There are 8 number of ways to make sum = 9.

• {2, 2, 5} = 2 + 2 + 5 = 9
• {2, 5, 2} = 2 + 5 + 2 = 9
• {5, 2, 2} = 5 + 2 + 2 = 9
• {3, 3, 3} = 3 + 3 + 3 = 9
• {2, 2, 2, 3} = 2 + 2 + 2 + 3 = 9
• {2, 2, 3, 2} = 2 + 2 + 3 + 2 = 9
• {2, 3, 2, 2} = 2 + 3 + 2 + 2 = 9
• {3, 2, 2, 2} = 3 + 2 + 2 + 2 = 9

Input: N = 2, X = 3, coins[] = {1, 2}
Output: 3
Explanation: There are 3 ways to make sum = 3

• {1, 1, 1} = 1 + 1 + 1 = 3
• {1, 2} = 1 + 2 = 3
• {2, 1} = 2 + 1 = 3

Approach: To solve the problem, follow the below idea:

The problem can be solved using Dynamic Programming. We can maintain a dp[] array, such that dp[i] stores the number of distinct ways to produce sum = i. We can iterate i from 1 to X, and find the number of distinct ways to make sum = i. For any sum i, we assume that the last coin used was the jth coin where j will range from 0 to N - 1. For jth coin, the value will be coins[j], so the number of distinct ways to make sum = i, if the last coin used was the jth coin is equal to dp[i - coins[j]] + 1. Similarly, for every coin we can assume that this coin was the last coin used to make sum = i, and add the number of ways to the final answer. The formula for the ith sum will be: dp[i] = sum(dp[i - coins[j]]), for all j from 0 to N - 1.

Also, the above formula will be true only when coins[j] >= i.

Step-by-step algorithm:

• Maintain a dp[] array such that dp[i] stores the number of distinct ways to make sum = i.
• Initialize dp[0] = 1 as there is only 1 way to make sum = 0, that is to not take any coin.
• Iterate i from 1 to X and calculate number of ways to make sum = i.
• Iterate j over all possible coins assuming the jth coin to be last coin which was selected to make sum = i and add dp[i – coins[j]] to dp[i].
• After all the iterations, return the final answer as dp[X].

Below is the implementation of the algorithm:

#include <bits/stdc++.h> #define ll long long int #define mod 1000000007 using namespace std; // function to find the number of distinct ways to make sum // = X ll solve(ll N, ll X, vector<ll>& coins) {  // dp[] array such that dp[i] stores the number of  // distinct ways to make sum = i  ll dp[X + 1] = {};  // There is only 1 way to make sum = 0, that is to not  // select any coin  dp[0] = 1;  // Iterate over all possible sums from 1 to X  for (int i = 1; i <= X; i++) {  // Iterate over all the N coins  for (int j = 0; j < N; j++) {  // Check if it is possible to have jth coin as  // the last coin to construct sum = i  if (coins[j] > i)  continue;  dp[i] = (dp[i] + dp[i - coins[j]]) % mod;  }  }  // Return the number of ways to make sum = X  return dp[X]; } int main() {  // Sample Input  ll N = 3, X = 9;  vector<ll> coins = { 2, 3, 5 };  cout << solve(N, X, coins) << "\n"; } 

import java.util.*; public class CoinChangeWays {  static final int MOD = 1000000007;  // Function to find the number of distinct ways to make sum = X  static long solve(int N, int X, List<Integer> coins) {  // dp[] array such that dp[i] stores the number of distinct ways  // to make sum = i  long[] dp = new long[X + 1];  // There is only 1 way to make sum = 0, that is to not select any coin  dp[0] = 1;  // Iterate over all possible sums from 1 to X  for (int i = 1; i <= X; i++) {  // Iterate over all the N coins  for (int j = 0; j < N; j++) {  // Check if it is possible to have jth coin as  // the last coin to construct sum = i  if (coins.get(j) > i) {  continue;  }  dp[i] = (dp[i] + dp[i - coins.get(j)]) % MOD;  }  }  // Return the number of ways to make sum = X  return dp[X];  }  public static void main(String[] args) {  // Sample Input  int N = 3, X = 9;  List<Integer> coins = Arrays.asList(2, 3, 5);  System.out.println(solve(N, X, coins));  } } // This code is contributed by shivamgupta0987654321 

using System; using System.Collections.Generic; public class CoinChangeWays {  static readonly int MOD = 1000000007;  // Function to find the number of distinct ways to make sum = X  static long Solve(int N, int X, List<int> coins)  {  // dp[] array such that dp[i] stores the number of distinct ways  // to make sum = i  long[] dp = new long[X + 1];  // There is only 1 way to make sum = 0, that is to not select any coin  dp[0] = 1;  // Iterate over all possible sums from 1 to X  for (int i = 1; i <= X; i++)  {  // Iterate over all the N coins  for (int j = 0; j < N; j++)  {  // Check if it is possible to have jth coin as  // the last coin to construct sum = i  if (coins[j] > i)  {  continue;  }  dp[i] = (dp[i] + dp[i - coins[j]]) % MOD;  }  }  // Return the number of ways to make sum = X  return dp[X];  }  public static void Main(string[] args)  {  // Sample Input  int N = 3, X = 9;  List<int> coins = new List<int> { 2, 3, 5 };  Console.WriteLine(Solve(N, X, coins));  } } 

// Function to find the number of distinct ways to make sum = X function solve(N, X, coins) {  // Initialize a dp array such that dp[i] stores the number of  // distinct ways to make sum = i  let dp = new Array(X + 1).fill(0);  // There is only 1 way to make sum = 0, that is to not  // select any coin  dp[0] = 1;  // Iterate over all possible sums from 1 to X  for (let i = 1; i <= X; i++) {  // Iterate over all the N coins  for (let j = 0; j < N; j++) {  // Check if it is possible to have jth coin as  // the last coin to construct sum = i  if (coins[j] > i)  continue;  dp[i] = (dp[i] + dp[i - coins[j]]) % 1000000007;  }  }  // Return the number of ways to make sum = X  return dp[X]; } // Sample Input let N = 3, X = 9; let coins = [2, 3, 5]; console.log(solve(N, X, coins)); 

# Importing the required libraries from typing import List # Defining the mod constant mod = 1000000007 def solve(N: int, X: int, coins: List[int]) -> int: # dp[] list such that dp[i] stores the number of # distinct ways to make sum = i dp = [0] * (X + 1) # There is only 1 way to make sum = 0, that is to not # select any coin dp[0] = 1 # Iterate over all possible sums from 1 to X for i in range(1, X + 1): # Iterate over all the N coins for j in range(N): # Check if it is possible to have jth coin as # the last coin to construct sum = i if coins[j] > i: continue dp[i] = (dp[i] + dp[i - coins[j]]) % mod # Return the number of ways to make sum = X return dp[X] def main(): # Sample Input N = 3 X = 9 coins = [2, 3, 5] print(solve(N, X, coins)) # Calling the main function if __name__ == "__main__": main() 

8 

Time Complexity: O(N * X), where N is the size of array coins[] and X is the sum we make using the coins.
Auxiliary Space: O(X)