FastPrepAll Subsets with a Given Sum
Problems/All Subsets with a Given Sum

All Subsets with a Given Sum

Apple logoApple● MediumNEW GRADPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in an Apple new grad phone screen. The report asks for all subsets that add up to a target, using backtracking. It did not share limits on the values, how to handle duplicates, or the order of the output. We chose those. Our version is about 90% the same as the reported question.

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)
All Apple interview questionsSee Apple hiring insights
Saved
class Solution {
    public int[][] subsetsWithSum(int[] arr, int target) {
        // Write your solution here.
    }
}
Checking account…