Solve Subset Sum And Return All Matching Subsets
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given an array of non-negative integers and a target, first determine whether any subset sums to the target using dynamic programming with `O(target)` space. Then implement a follow-up that returns all subsets whose values sum to the target.
Function signature:
```python
def subset_sum_exists(arr: list[int], target: int) -> bool:
pass
def all_subsets_with_sum(arr: list[int], target: int) -> list[list[int]]:
pass
```
Constraints:
- `arr` contains non-negative integers.
- `target >= 0`.
- For the existence function, use `O(target)` auxiliary space.
- For the all-subsets function, exponential output size is expected.
- Subsets should respect element positions; equal values at different indexes are distinct choices.
Examples:
```text
arr = [2, 3, 7, 8, 10], target = 11
subset_sum_exists returns True because 3 + 8 = 11.
```
```text
arr = [1, 2, 2], target = 3
all_subsets_with_sum may return [[1,2], [1,2]] for the two different 2 positions.
```
Quick Answer: Practice subset-sum interview variants, from an O(target) dynamic programming existence check to returning all matching subsets. The prompt emphasizes DP state, backtracking, duplicate values by index, exponential output size, and complexity analysis.
Return all subsets whose values sum to target. Equal values at different indexes are distinct choices. Return subsets sorted lexicographically for deterministic output.
Constraints
- Non-negative integers are assumed.
- Duplicate values at different indexes are distinct choices.
Examples
Input: ([2,3,7,8,10], 11)
Expected Output: [[3,8]]
Input: ([1,2,2], 3)
Expected Output: [[1,2],[1,2]]
Input: ([], 0)
Expected Output: [[]]
Input: ([], 5)
Expected Output: []
Input: ([0,0], 0)
Expected Output: [[],[0],[0],[0,0]]
Input: ([1,1,1], 2)
Expected Output: [[1,1],[1,1],[1,1]]
Input: ([5], 5)
Expected Output: [[5]]
Input: ([4,6,10], 3)
Expected Output: []
Hints
- For the boolean version, use DP.
- For all subsets, exponential output is unavoidable.