All Subsets with a Given Sum
Updated
Problem statement
Given an array arr of distinct positive integers and a nonnegative integer target, return every subset whose sum equals target. Each array element may be used at most once.
List each subset in increasing numeric order. List the subsets in lexicographic order: compare the first differing values, with the smaller value first; if one list is a prefix of the other, put the shorter list first.
The empty subset has sum zero and must be returned when target is zero. Return an empty list when no subset works. Use backtracking for the final approach, and discuss the exponential search cost and the space used by returned subsets.
Function
subsetsWithSum(arr: int[], target: int) → int[][]Examples
Example 1
arr = [3,1,2,5]target = 5return = [[2,3],[5]]The subsets [2,3] and [5] both sum to 5. No other subset does. Since 2 is less than 5, [2,3] comes first.
Example 2
arr = [2,4]target = 0return = [[]]The empty subset sums to zero. Every nonempty subset has a positive sum, so the empty subset is the only result.
Constraints
- 0 <= arr.length <= 16.
- Every value in arr is between 1 and 100, inclusive.
- All values in arr are distinct.
- 0 <= target <= 1600.
More Apple Phone Screen questions
- Subarray Product Less Than KPHONE SCREEN · Seen Nov 2026
- Evaluate DivisionPHONE SCREEN · Seen Nov 2026
- Reverse a Linked ListPHONE SCREEN · Seen Nov 2026
- Validate a BST with a Custom ComparisonPHONE SCREEN · Seen Nov 2026
- Design a Food Rating SystemPHONE SCREEN · Seen Oct 2026
- Days Until Poisoned Plants StabilizePHONE SCREEN · Seen Oct 2026
- Capture Surrounded Regions with Union-FindPHONE SCREEN · Seen Oct 2026
- Maintain a Consistent-Hashing RingPHONE SCREEN · Seen Oct 2026
- Count Nodes in a ChainPHONE SCREEN · Seen Oct 2026
- Run-Length DecodingPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Combination Sum with Reusable ValuesPinterest · PHONE SCREENPinterest interview questions
- Validate a Mahjong Hand PartitionDuolingo · PHONE SCREENDuolingo interview questions
- Combination Sum With Unlimited ReuseMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- All Subsequences with Sum KExpedia · ONSITE INTERVIEWExpedia interview questions
- Binary Tree Target-Sum PathsByteDance · PHONE SCREENByteDance interview questions
- Count Complete Tic-Tac-Toe GamesDecagon · PHONE SCREEN · ONSITE INTERVIEWDecagon interview questions
- SubsetsTemu · PHONE SCREENTemu interview questions
- Filter Data with Composable PredicatesCoreWeave · PHONE SCREEN
- PermutationsEPAM · PHONE SCREENEPAM interview questions
- Permutations of Unique CharactersSalesforce · PHONE SCREENSalesforce interview questions
Apple interview experiences
- Apple SWE Phone Screen: Subarray Products: 1 Experience
- Apple New Grad SWE Java, Coding and Manager Rounds: 1 Experience
- Apple AI Coding and Related Interviews: 17 Experiences
- Apple India SWE New Grad Interviews: 5 Experiences
- Apple New Grad SWE Phone Screens: 12 Experiences (Part 3 of 3)
- Apple New Grad SWE and Embedded: 16 Experiences (Part 2 of 3)