Below, for an integer sequence, its subsequence sum is the sum of elements of its subsequence.

We assume \(A_i\) is sorted in ascending order.

We define a set \(EX_i\) as the set of the non-negative integers at most \(S_i := A_1 + A_2 + ... + A_i\) that are not a subsequence sum of \((A_1, A_2, ..., A_i)\). For convenience, we set \(EX_0 = \{\}\) and consider calculating \(EX_i\) from \(EX_{i-1}\). Depending on the values of \(A\), \(EX_i\) might become quite a large set. However, until the smallest \(K\) integers belonging to \(EX_N\) are determined, it doesn’t grow too large, and we have \(|EX_i| \leq Ki\). Below, we will prove this inductively.

Considering \(EX_i\) with respect to \(EX_{i-1}\), we consider the following cases:

[1] When \(S_{i-1} < A_i\)

Due to the monotonicity of \(A\), the following cannot be a subsequence sum of \(A\):

• integers in \(EX_{i-1}\), and
• integers greater than or equal to \(S_{i-1} + 1\) and less than \(A_i\).

Furthermore, these are all of the elements of \(EX_N\) that are less than \(A_i\). The number of such integers is \(|EX_{i-1}| + A_i - S_{i-1} - 1\), and if this is greater than or equal to \(K\), the \(K\) integers we are seeking are determined (★).

Consider when it is less than \(K\). \(EX_i\) can be divided into the following three types of integers:

• integers in \(EX_{i-1}\),
• integers greater than or equal to \(S_{i-1} + 1\) and less than \(A_i\), and
• integers \(x\) greater than or equal to \(A_i\) and less than \(S_i\) satisfying \(x - A_i \in EX_{i-1}\).

The number of integers of the second and third types is \(|EX_{i-1}| + A_i - S_{i-1} - 1\), which we assumed to be less than \(K\), so we have \(|EX_i| \leq |EX_{i-1}| + K\).

[2] When \(A_i \leq S_{i-1}\)

Due to the monotonicity of \(A\), the following cannot be a subsequence sum of \(A\):

• integers less than \(A_i\) and in \(EX_{i-1}\).

Furthermore, this is all of the elements of \(EX_N\) that are less than \(A_i\). If the number of such integers is greater than or equal to \(K\), the \(K\) integers we are seeking are determined (★).

Consider when it is less than \(K\). \(EX_i\) can be divided into the following three types of integers:

• integers less than \(A_i\) and in \(EX_{i-1}\),
• integers \(x\) between \(A_i\) and \(S_{i-1}\), inclusive, satisfying \(x \in EX_{i-1}\) and \(x - A_i \in EX_{i-1}\), and
• integers \(x\) between \(S_{i-1} + 1\) and \(S_i\), inclusive, satisfying \(x - A_i \in EX_{i-1}\).

The first and second types of integers are elements of \(EX_{i-1}\), and their count is less than or equal to \(|EX_{i-1}|\). The number of the third type of integers, paying attention to \(x \in EX_{i-1} \iff S_{i-1} - x \in EX_{i-1}\), is the same as the number of the first type of integers. Since we assumed this to be less than \(K\), we have \(|EX_i| \leq |EX_{i-1}| + K\).

Therefore, as long as ★ does not happen and the answer is not confirmed, we have \(|EX_i| \leq |EX_{i-1}| + K\), and by induction, we can conclude that \(|EX_i| \leq Ki\).

Thus, if we print the answer immediately when ★ happens while maintaining \(EX_i\) straightforwardly, it takes \(O(N^2K\log {(NK)})\) time (if std::set is used to maintain them).

(Modified the first draft written by GPT-4.)