Closest Subset Sum to (50)

You are given a list of integers representing the difficulty levels of various tricks. Your task is to select a subset of these integers such that the total sum is as close as possible to \(50\). In case of a tie (i.e. two subset sums are equally distant from \(50\)), choose the one with the larger sum.

For example, if you have tricks with difficulties [25, 25], the best total is 50 since \(25+25=50\). If the input is [1, 2, 3, 4, 5], the best sum is 15 though it is less than \(50\). When no tricks are provided (an empty list), the output should be 0.

The problem can be approached using dynamic programming where you keep track of all possible sums that can be computed from a subset of the given list and choose the one that minimizes the absolute difference with \(50\) (with ties broken in favor of the larger sum).

inputFormat

The first line of input contains a single integer \(n\) representing the number of trick difficulty levels. The second line contains \(n\) space-separated integers representing the difficulty levels.

Note: When \(n = 0\), the second line will be empty.

outputFormat

Output a single integer: the sum of a subset of the given trick difficulties that is as close as possible to \(50\). In case of a tie, output the larger sum.

1
50

50