Katkat
Back

Solve Subset Sum And Return All Matching Subsets

AppleSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to navigate the trade-off between dynamic programming and backtracking to find all unique combinations of elements that sum to a target value.

Problem Statement

Given an array of integers nums and an integer target, return all unique subsets (combinations) of nums that sum up to target. Each number in nums may only be used once in the combination. The solution set must not contain duplicate combinations.

Function Signature

def find_all_subsets(nums: List[int], target: int) -> List[List[int]]:

Constraints

  • 1 <= len(nums) <= 30
  • 1 <= nums[i] <= 100
  • 1 <= target <= 500
  • The result can be large; focus on an efficient backtracking approach.

Examples

Example 1: Input: nums = [10, 1, 2, 7, 6, 1, 5], target = 8 Output: [[1, 1, 6], [1, 2, 5], [1, 7], [2, 6]]

Example 2: Input: nums = [2, 5, 2, 1, 2], target = 5 Output: [[1, 2, 2], [5]]

Edge Cases

  • Empty nums array.
  • target is smaller than any element in nums.
  • No combinations sum to target (return an empty list).
  • nums contains duplicate values.

Hints

Hint 1

Sort the input array first to easily identify and skip duplicate elements during the recursion process.

Hint 2

Use a backtracking approach where you explore two branches for each element: including it in the current sum or excluding it.

Hint 3

To avoid duplicate combinations, when you encounter identical numbers in the same recursion level, skip all but the first instance.

Follow-up questions

  • How does the time complexity change if you are only asked to return the count of subsets rather than the subsets themselves?
  • If the constraints on `target` were much larger but `nums` remained small, how could you optimize the space complexity using memoization?
  • What modifications would be necessary if the problem allowed each element in `nums` to be used an infinite number of times?