Amazon Online Assessment (OA) - Optimizing Box Weights

Given a multiset (set bt allows for multiple instances of same value), partition it into two multisets A and B such that the sum of A is greater than that of B. Return A. If more than one such As exists, return the one with minimal size.

Examples

Example 1:

Input:

nums = [4, 5, 2, 3, 1, 2]

Output:

[4, 5]

Explanation:

We can divide the numbers into two subsets A = [4, 5] and B = [1, 2, 2, 3]. The sum of A is 9 which is greater than the sum of B which is 8. There are other ways to divide but A = [4, 5] is of minimal size of 2.

Try it yourself

Solution