FastPrepTop K Subset Sums of Nonnegative Weights

Top K Subset Sums of Nonnegative Weights

Google logoGoogle● HardNEW GRADPHONE SCREEN
Learn

Problem statement

You are given distinct objects whose non-negative integer weights are stored in weights, and an integer k.

Every subset of objects contributes one subset sum, including the empty subset. Different subsets are counted separately even when their sums are equal.

Return the largest k subset sums in nonincreasing order.

Function

topKSubsetSums(weights: int[], k: int) → long[]

Examples

Example 1

weights = [1,2,4]k = 5return = [7,6,5,4,3]

The five largest sums among all eight subsets are 7, 6, 5, 4, 3.

Example 2

weights = [2,3]k = 4return = [5,3,2,0]

All four subset sums are returned.

Example 3

weights = [0,5]k = 4return = [5,5,0,0]

The zero-weight object creates different subsets with equal sums, and each subset is retained.

Constraints

  • 1 <= weights.length <= 40.
  • 0 <= weights[i] <= 1000000000.
  • 1 <= k <= min(100000, 2^weights.length).

More Google problems

See Google hiring insights
public long[] topKSubsetSums(int[] weights, int k) {
    // Write your code here.
}
weights[1,2,4]
k5
expected[7,6,5,4,3]
Checking account…