Official Analysis (C++)

Explanation

Let $\texttt{dp[i][j]}$ represent whether it's possible to select a group of coins such that a subset of them sum to $i$ and the rest of them in the group sum to $j$. This way we'll have coins whose sum is $i + j$, and we're interested in cases where $i + j = k$.

Our base case is $\texttt{dp[0][0] = 1}$ representing an empty selection. Now for each coin, we can update our DP array by considering two possibilities:

1. Include the coin in Arya's part
2. Include the coin in the rest of the selection

Finally we collect all the values $x$ such that $\texttt{dp[x][k - x]}$ is true which are eventually the values Arya can form.

Implementation

Time Complexity: $\mathcal{O}(NK^2)$

Copy
#include <iostream>
#include <vector>

int main() {
	int n, k;
	std::cin >> n >> k;
	std::vector<int> coins(n);
	for (int &x : coins) { std::cin >> x; }

	std::vector dp(k + 1, std::vector<int>(k + 1));

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

public class TheValuesYouCanMake {
	public static void main(String[] args) {
		Kattio io = new Kattio();
		int n = io.nextInt();
		int k = io.nextInt();

		int[] coins = new int[n];

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

dp = [[0] * (k + 1) for _ in range(k + 1)]
dp[0][0] = 1

for a in coins:
	new_dp = [x[:] for x in dp]
	for i in range(k + 1):
		for j in range(k - i + 1):