Smallest Difference of Subsequence Sums

Given an integer \(N\) and a list of \(N\) integers, consider all non-empty subsequences of the list. A subsequence is any subset of the elements (the order in the original list is not relevant). Your task is to compute the smallest possible value of the absolute difference between the sums of any two distinct (non-overlapping) subsequences.

Note: The two subsequences must be chosen independently (they may originate from different selections of indices) and are not required to be contiguous. For a single element list, the answer is the absolute value of that element.

Formally, if \(S_1\) and \(S_2\) are the sums obtained from any two non-empty subsequences of the array with \(S_1 \neq S_2\) (or even if equal, they are chosen as two distinct selections), find the minimum value of \(|S_1 - S_2|\) over all possible pairs.

The answer should be computed by considering all non-empty subsequences.

inputFormat

The input is read from standard input (stdin) and has the following format:

• The first line contains a single integer \(N\) (the number of elements in the sequence).
• The second line contains \(N\) space-separated integers representing the elements of the sequence.

outputFormat

Output a single integer representing the smallest possible absolute difference between the sums of any two non-empty subsequences. The output should be printed to standard output (stdout).

5
3 1 4 1 5

0