← Amazon questions

Find any subsequence with zero sum

Filed under Amazon

Free read 3 of 3

The 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

  1. The brute force approach is to check all 2^n subsets, which is O(2^n).

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.