Minimum Subset Sum Difference
Updated
Problem statement
You are given an array nums of positive integers. Put every number into one of two groups, so that each number is in exactly one group. A group may be empty.
Return the smallest possible absolute difference between the sum of one group and the sum of the other group.
Numbers at different positions are separate items, even when they are equal.
Function
minimumSubsetSumDifference(nums: int[]) → intExamples
Example 1
nums = [3,9,7,3]return = 2The total is 3 + 9 + 7 + 3 = 22, so a perfect split would need a group that adds up to 11. No group can: the group sums that come closest are 10 (7 + 3) and 12 (9 + 3). Putting [9, 3] in one group and [3, 7] in the other gives sums 12 and 10, so the answer is 12 - 10 = 2.
Example 2
nums = [5,5,4,3,3]return = 0The total is 20. The groups [5, 5] and [4, 3, 3] both add up to 10, so the difference is 0.
Always adding the next largest number to the smaller group does not find this. It builds [5, 4] and [5, 3, 3], with sums 9 and 11, a difference of 2.
Example 3
nums = [8]return = 8There is only one number. One group gets it and the other group stays empty, so the sums are 8 and 0 and the difference is 8.
Constraints
1 <= nums.length <= 301 <= nums[i] <= 1000
More Expedia Onsite Interview questions
- Scramble StringONSITE INTERVIEW · Seen Sep 2026
- Smallest Sufficient TeamONSITE INTERVIEW · Seen Sep 2026
- Check Anagram Pairs Index by IndexONSITE INTERVIEW · Seen Oct 2025
- Fresh Oranges Left After Rotting StopsONSITE INTERVIEW · Seen Oct 2025
- Longest Increasing SubsequenceONSITE INTERVIEW · Seen Oct 2025
- Lowest Common Ancestor with Repeated and Missing ValuesONSITE INTERVIEW · Seen Oct 2025
- Shortest Substring with Exactly K OnesONSITE INTERVIEW · Seen Oct 2025
- Middle Element of a Linked ListONSITE INTERVIEW · Seen Nov 2024
- Minimum in a Rotated Sorted ArrayONSITE INTERVIEW · Seen Sep 2024
- Mirror Image Binary TreesONSITE INTERVIEW · Seen Sep 2024
Similar questions at other companies
- Count Subsets With a Target SumSafe Security · ONSITE INTERVIEW
- 0/1 Knapsack with Weight and Volume LimitsGoogle · ONSITE INTERVIEWGoogle interview questions
- 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
- Word BreakAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Maximum SubarrayUpstart · ONSITE INTERVIEWUpstart 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
Interview reports that mention this question
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)