CSES Solutions – Money Sums
You have N coins with certain values. Your task is to find all money sums you can create using these coins.
Examples:
Input: N = 4, coins[] = {4, 2, 5, 2}
Output:
9
2 4 5 6 7 8 9 11 13
Explanation:
- To create sum = 2, we can use the coin with value = 2.
- To create sum = 4, we can use both the coins with value = 2.
- To create sum = 5, we can use the coin with value = 5.
- To create sum = 6, we can use coin with value = 2 and coin with value = 4.
- To create sum = 7, we can use coin with value = 2 and coin with value = 5.
- To create sum = 8, we can use both the coins with value = 2 and another coin with value = 4.
- To create sum = 9, we can use coin with value = 4 and coin with value = 5.
- To create sum = 11, we can use coin with value = 2, coin with value = 4 and coin with value = 5.
- To create sum = 13, we can use both the coins with value = 2, coin with value = 4 and coin with value = 5.
Input: N = 10, coins[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Output:
10
1 2 3 4 5 6 7 8 9 10
Approach: To solve the problem, follow the below idea:
The problem can be solved using Dynamic Programming. We’ll define dp[][], such that dp[i][j] = true if it is possible to make a sum of j with i coins and dp[i][j] = false if it is impossible to make a sum of j with i coins. Iterate through all the coins i and possible sums j:
- If dp[i – 1][j] = true, then dp[i][j] = true because if it is possible to make a sum of j with (i-1) coins, then we can make the same sum with i coins as well.
- Else if dp[i – 1][j – coins[i]] = true, then dp[i][j] = true because if it is possible to make a sum of (j – coins[i]) with i – 1 coins, then we can make sum j by using the ith coin.
For all values of j, dp[N][j] will store whether it is possible to create sum j or not.
Step-by-step algorithm:
- Maintain a boolean dp[][] array such that dp[i][j] = true if it is possible to make sum j using first i coins.
- Initialize a variable sum to store the sum of all coins.
- Iterate over each coin from i = 1 to N
- Iterate over each sum j = 0 to j <= sum,
- If dp[i – 1][j] = true, dp[i][j] = true
- Else if dp[i – 1][j – coins[i]] = true,
- Else dp[i][j] = false
- Iterate over each sum j = 0 to j <= sum,
- Store the sums j from 1 to sum which are possible to construct, that is dp[N][j] = true
- Print the number of possible sums along with all the possible sums.
Below is the implementation of the algorithm:
#include <bits/stdc++.h>
#define ll long long
using namespace std;
// Function to print all the possible sums
void solve(vector<ll>& coins, ll N)
{
// Find the maximum value which we can make using all
// the coins
ll sum = accumulate(coins.begin(), coins.end(), 0LL);
// dp[][] array such that dp[i][j] = true if it is
// possible to construct sum j using i coins
vector<vector<bool> > dp(N + 1,
vector<bool>(sum + 1, false));
dp[0][0] = true;
// Iterate over all the coins
for (int i = 1; i <= N; i++) {
// Iterate over all the sums
for (int j = 0; j <= sum; j++) {
// If it is possible to construct sum j using
// (i-1) coins, then mark dp[i][j] = true
dp[i][j] = dp[i - 1][j];
// If it is possible to construct sum (j -
// coins[i]) using (i - 1) coins, then mark
// dp[i][j] = true
if (j >= coins[i - 1]
&& dp[i - 1][j - coins[i - 1]]) {
dp[i][j] = true;
}
}
}
// vector to store all the sums which are possible to
// construct using all the coins
vector<int> possibleSums;
// Store all the possible sums from 1 to sum which are
// possible to construct
for (int j = 1; j <= sum; j++) {
if (dp[N][j]) {
possibleSums.push_back(j);
}
}
// Print the number of possible sums
cout << possibleSums.size() << endl;
// Print all the possible sums
for (int i = 0; i < possibleSums.size(); i++)
cout << possibleSums[i] << " ";
cout << endl;
}
int main()
{
// Sample Input
ll N = 4;
vector<ll> coins = { 4, 2, 5, 2 };
solve(coins, N);
}
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
int N = 4;
int[] coins = {4, 2, 5, 2};
gfg(N, coins);
}
public static void gfg(int N, int[] coins) {
// Calculate the sum of the all coins
int sum = 0;
for (int coin : coins) {
sum += coin;
}
boolean[][] dp = new boolean[N + 1][sum + 1];
// Base case: When no coins are selected and sum = 0 is possible
dp[0][0] = true;
for (int i = 1; i <= N; i++) {
// Iterate over each sum j from the 0 to sum
for (int j = 0; j <= sum; j++) {
if (dp[i - 1][j]) {
dp[i][j] = true;
} else if (j - coins[i - 1] >= 0 && dp[i - 1][j - coins[i - 1]]) {
dp[i][j] = true;
}
}
}
// Initialize a list to store the possible sums
List<Integer> possibleSums = new ArrayList<>();
for (int j = 1; j <= sum; j++) {
if (dp[N][j]) {
possibleSums.add(j);
}
}
// Print the number of the possible sums
System.out.println(possibleSums.size());
// Print the possible sums separated by the space
for (int i = 0; i < possibleSums.size(); i++) {
System.out.print(possibleSums.get(i) + " ");
}
}
}
function GFG(N, coins) {
// Calculate the sum of all coins
let sum = coins.reduce((acc, curr) => acc + curr, 0);
let dp = new Array(N + 1).fill(false).map(() => new Array(sum + 1).fill(false));
dp[0][0] = true;
// Iterate over each coin from i = 1 to N
for (let i = 1; i <= N; i++) {
// Iterate over each sum j from 0 to sum
for (let j = 0; j <= sum; j++) {
if (dp[i - 1][j]) {
dp[i][j] = true;
}
else if (j - coins[i - 1] >= 0 && dp[i - 1][j - coins[i - 1]]) {
dp[i][j] = true;
}
}
}
// Initialize an array to the store the possible sums
let possibleSums = [];
for (let j = 1; j <= sum; j++) {
if (dp[N][j]) {
possibleSums.push(j);
}
}
// Print the number of the possible sums
console.log(possibleSums.length);
console.log(possibleSums.join(' '));
}
// Example usage:
const N = 4;
const coins = [4, 2, 5, 2];
GFG(N, coins);
from typing import List
# Function to print all the possible sums
def solve(coins: List[int], N: int):
# Find the maximum value which we can make using all the coins
sum_coins = sum(coins)
# dp[][] array such that dp[i][j] = true if it is possible to construct sum j using i coins
dp = [[False for _ in range(sum_coins + 1)] for _ in range(N + 1)]
dp[0][0] = True
# Iterate over all the coins
for i in range(1, N + 1):
# Iterate over all the sums
for j in range(sum_coins + 1):
# If it is possible to construct sum j using (i-1) coins, then mark dp[i][j] = true
dp[i][j] = dp[i - 1][j]
# If it is possible to construct sum (j - coins[i]) using (i - 1) coins, then mark dp[i][j] = true
if j >= coins[i - 1] and dp[i - 1][j - coins[i - 1]]:
dp[i][j] = True
# list to store all the sums which are possible to construct using all the coins
possible_sums = []
# Store all the possible sums from 1 to sum which are possible to construct
for j in range(1, sum_coins + 1):
if dp[N][j]:
possible_sums.append(j)
# Print the number of possible sums
print(len(possible_sums))
# Print all the possible sums
print(*possible_sums)
# Sample Input
N = 4
coins = [4, 2, 5, 2]
solve(coins, N)
Output
9 2 4 5 6 7 8 9 11 13
Time Complexity: O(N * X), where N is the number of coins and X is the sum of values of all coins
Auxiliary Space: O(N * X)
Contact Us