How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Return top-k subset sums in descending order

Q: Return top-k subset sums in descending order

This question evaluates proficiency in combinatorial reasoning, algorithmic optimization for large search spaces, and efficient extraction of top-k values within the coding & algorithms domain.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

## Problem You are given **n distinct objects**, each with a **non-negative integer weight**. A **subset** can be any selection of these objects (including the empty subset). Define the **weight of a subset** as the sum of weights of the objects in that subset. ### Task Return the **k subset weights** with the **largest sums**, sorted in **descending** order. ### Input - An integer array `w` of length `n` (`w[i] >= 0`), where all objects are distinct. - An integer `k`. ### Output - A list/array of length `k` containing the **k largest subset sums** in **non-increasing** order. ### Notes / Clarifications - Different subsets may have the same sum; treat them as separate results if they correspond to different subsets. - You may assume `1 <= k <= 2^n`. ### Example If `w = [3, 2, 1]`: - Subset sums are: `0, 1, 2, 3, 3, 4, 5, 6` - The top `k=4` sums (descending) are: `[6, 5, 4, 3]` ### Constraints (typical interview-style) - `1 <= n <= 2e5` (or large enough that enumerating all `2^n` subsets is infeasible) - `0 <= w[i] <= 1e9` - `1 <= k <= min(2^n, 2e5)`

Quick Answer: This question evaluates proficiency in combinatorial reasoning, algorithmic optimization for large search spaces, and efficient extraction of top-k values within the coding & algorithms domain.

You are given an array `w` of non-negative integer weights. Each position represents a distinct object, so two different subsets are considered different even if they produce the same total weight. A subset may contain any selection of objects, including the empty subset. The weight of a subset is the sum of the selected weights. Return the `k` largest subset sums, sorted in descending order (non-increasing, so duplicates may appear).

Constraints

1 <= len(w) <= 2 * 10^5
0 <= w[i] <= 10^9
1 <= k <= min(2^len(w), 2 * 10^5)
Use 64-bit integers for subset sums in languages with fixed-width integer types

Examples

Input: ([3, 2, 1], 4)

Expected Output: [6, 5, 4, 3]

Explanation: All subset sums are 0, 1, 2, 3, 3, 4, 5, 6. The top 4 in descending order are [6, 5, 4, 3].

Input: ([5], 2)

Expected Output: [5, 0]

Explanation: The only subsets are {} with sum 0 and {5} with sum 5.

Input: ([0, 2, 2], 6)

Expected Output: [4, 4, 2, 2, 2, 2]

Explanation: Different subsets can have the same sum. The 8 subset sums are 0, 0, 2, 2, 2, 2, 4, 4, so the top 6 are [4, 4, 2, 2, 2, 2].

Input: ([4, 1, 1], 8)

Expected Output: [6, 5, 5, 4, 2, 1, 1, 0]

Explanation: This requests all 2^3 subset sums. In descending order they are [6, 5, 5, 4, 2, 1, 1, 0].

Input: ([0, 0, 0], 5)

Expected Output: [0, 0, 0, 0, 0]

Explanation: Every subset has sum 0, so every returned value is 0.

Hints

If `total = sum(w)`, then every subset sum can be written as `total - removed_sum`, where `removed_sum` is the sum of the elements not chosen. So the largest subset sums correspond to the smallest removed sums.
After sorting the weights in ascending order, you can generate the next smallest removed sum with a min-heap instead of enumerating all `2^n` subsets.

Quick Overview

This question evaluates proficiency in combinatorial reasoning, algorithmic optimization for large search spaces, and efficient extraction of top-k values within the coding & algorithms domain.