FastPrepDistinct Subset Sums
Problems/Distinct Subset Sums

Distinct Subset Sums

Google logoGoogle● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionExamples

Problem statement

Source note: This was one of two questions in an extra virtual DSA round at Google, which the recruiter added after an earlier coding round went badly. The task was to list every different total that some subset of an integer array can reach.

The post gives no examples, limits or output format. Here the empty subset counts (so 0 is always listed), the totals come back sorted, and the array has at most 50 numbers from -20 to 20.

The judged task matches the post at about 85%.

You are given an integer array nums. A subset is any choice of elements of nums, taken by position, including the empty choice. The sum of the empty subset is 0.

The problem statement continues
Pro

Examples

Example 1

nums = [1,2,3]return = [0,1,2,3,4,5,6]

The subsets give 0 (empty), 1, 2, 3, 1 + 2 = 3, 1 + 3 = 4, 2 + 3 = 5 and 1 + 2 + 3 = 6. The sum 3 shows up twice but is listed once, so the answer is [0,1,2,3,4,5,6].

02 · Example 2
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week

More Google Onsite Interview questions

  • Evaluate a Nested Math ExpressionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Playlist With No Same Artist in a RowONSITE INTERVIEW · Seen Nov 2026
  • Route Pattern MatcherPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Delete Nodes and Return Forest RootsONSITE INTERVIEW · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • First and Last Target Position in a Mountain ArrayONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • 0/1 Knapsack with Weight and Volume LimitsONSITE INTERVIEW · Seen Nov 2026
  • Batched Subsequence Word MatchesONSITE INTERVIEW · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Maximal SquareAmazon · ONSITE INTERVIEW
  • Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
  • Maximum Subarray Sum with One DeletionOracle · ONSITE INTERVIEWOracle interview questions
  • Best Time to Buy and Sell Stock IIKotak Mahindra Bank · ONSITE INTERVIEWKotak Mahindra Bank interview questions
  • Coin ChangeMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
  • Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart interview questions
  • Smallest Sufficient TeamExpedia · ONSITE INTERVIEWExpedia interview questions
  • Maximum Product SubarrayHartford Financial Services · ONSITE INTERVIEWHartford Financial Services interview questions
  • Word BreakMoveworks · ONSITE INTERVIEWMoveworks interview questions
  • Maximum Value from Circular HousesDigitalOcean · ONSITE INTERVIEWDigitalOcean interview questions

Google interview experiences

  • Google L5 Security Engineer Domain Knowledge Round: 1 Experience
  • Google Software Engineer Onsite Questions: 10 Experiences
  • Google OA: What It Tests (2026)
  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
CodePython 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
from collections import defaultdict
 
class Solution:
def solve(self, values, queries):
# Build the adjacency structure
n = len(values)
graph = defaultdict(list)
for u, v in queries:
graph[u].append(v)
 
best = [float("inf")] * n
heap = [(0, 0)]
while heap:
cost, node = heapq.heappop(heap)
if cost > best[node]:
continue
Run and Submit unlock with Pro
FastPrep Pro
Reported in 1 Google interview this week

Unlock this recently reported problem

FastPrep Pro gives you full access to interview problems reported within the last week.

  • Full problem statement and constraints
  • 2 more worked examples, explained
  • Guided hints and editorial
  • Run your code on real test cases
$8.25/month

$99 billed yearly — or $19 month-to-month. Cancel anytime.

Free plan — 2 of 2 free unlocks used this week