Find any subsequence with zero sum
Filed under Amazon
Free read 3 of 3The brute force approach is to check all 2^n subsets, which is O(2^n).
The question
Given an array of integers, determine if there exists a non-empty subsequence that sums to zero and return it.
Constraints
- Array can contain positive and negative integers
- Return any valid subsequence
- Time complexity should be O(n^2) or better
Examples
- Input
- [3, 4, -7, 1]
- Output
- [3, 4, -7]
- Why
- 3 + 4 - 7 = 0
Approach
The brute force approach is to check all 2^n subsets, which is O(2^n).
Split the array into two halves, generate all subset sums for both, and look for a match that sums to zero.
Use a set to store reachable sums. For each element, update the set of reachable sums. If 0 is reached, backtrack to find the elements.
Tips
- What they are testing: Test with arrays containing only positive numbers (should return null/empty) and arrays with zero.
- Common mistake: Confusing 'subsequence' with 'subarray'. A subsequence does not need to be contiguous.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.