# Maximum Equal Sum K Subsequences

Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum. Example:

A = [1, 2, 3, 4, 6] & K = 2
Maximum Sum Subsequence = 8 = [2, 6] & [1, 3, 4]

If, K = 3 and A = [1, 2, 3, 4, 6, 8, 9]
Maximum Sum Subsequence = 11 = [9, 2] & [8, 3] & [6, 4, 1]

It is not necessary that all the elements of the array need to be a part of the subsequences but each element can only be part of 1 subsequence.

I tried a brute force approach with Knapsack but that doesnt work. Any better approaches or optimizations?

• Rather than answering in the comments, please edit the question to make it clear, so that people who read the question can understand the problem without having to read the comments. Thank you. – D.W. Sep 10 '18 at 17:29

This problem is NP-complete by reduction to the given subset sum problem, which asks if there is a subset $S$ from a set with a certain sum $n$.
Suppose we are given such an instance and that your problem can be efficiently solved. Then we can transform the instance by making $S' = S \cup \{x, x - n\}$ for some sufficiently large $x$ and solving your problem to find the $K = 2$ maximum equal subsequence sums. Then iff the answer includes $x$ and $x - n$ there is a subset that sums to $n$ and we efficiently solved the given subset sum problem.
• @user248884 $n$ is defined in the first sentence. I don't know what exactly is unclear for me to elaborate on. – orlp Sep 11 '18 at 6:24
• Consider a case where A = [1,2,3,4,6,8,9] & $K$ = 3. Applying subset sum, we get that 1,2,3,4 can be part of the subsequence, so K = 1. For the next iteration, we remove 1,2,3,4 from the array so A = [6,8,9]. This returns false as a subsequence of 10 cannot be made. But, infact the subsequence of 10 is possible (Eg: [1,9], [2, 8], [4,6]) if the elements were sampled differently. I wanted elaboration on such cases. Sorry for not making it clear earlier. – user248884 Sep 11 '18 at 7:40