CSES - Money Sums

Official Editorial

Explanation

For this problem, we'll define $\texttt{dp[i][j]}$ as if it is possible to make a sum of $j$ with $i$ coins.

And if we loop through all the coins and possible sums, then we'll get two possible situations:

If it is possible to make a sum of $j$ with less than $i$ coins, then make the same sum with more than $i$ coins will also be possible.

And if it is possible to make a sum of $\texttt{current\_sum - coin\_value[i]}$ with $i - 1$ coins, then make a sum of $\texttt{current\_sum}$ with $i$ coins will also be possible.

And at the end, we can loop through the $\texttt{dp}$ array, find all the possible $\texttt{sums}$ with $n$ coins, put them in a dynamic array, then print out the size of that dynamic array and every elements in it.

Implementation

Time Complexity: $\mathcal{O}(N\cdot X)$

Copy
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100;
const int MAX_SUM = 1e5;

bool dp[MAX_N + 1][MAX_SUM + 1];

int main() {

Copy
import java.io.*;
import java.util.*;

public class MoneySums {
	public static int maxSum = (int)1e5;

	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();

		int N = io.nextInt();

Copy
n = int(input())
money = list(map(int, input().split()))

max_sum = n * 1000
dp = [[False] * (max_sum + 1) for _ in range(n + 1)]
dp[0][0] = True

for i in range(1, n + 1):
	for j in range(max_sum + 1):
		dp[i][j] = dp[i - 1][j]