Minimum Difficulty Difference

You are given a set of M problems, each with a certain difficulty value. Let the list of difficulties be \(D = [D_1, D_2, \dots, D_M]\). Your task is to partition these problems into two groups such that the absolute difference between the sum of difficulties of each group is minimized.

Let \(S = \sum_{i=1}^M D_i\), and assume one group gets a total difficulty of \(S_1\) and the other gets \(S_2 = S - S_1\). You need to minimize the value of \(|S_1 - S_2|\), which can be reformulated as finding a subset of \(D\) whose sum is as close as possible to \(\frac{S}{2}\).

This problem involves dynamic programming and is analogous to the partition or subset sum problem.

inputFormat

The input is read from standard input (stdin) and is formatted as follows:

• The first line contains a single integer M, the number of problems.
• The second line contains M space-separated integers, representing the difficulty values \(D_1, D_2, \dots, D_M\).

outputFormat

The output should be written to standard output (stdout) and is a single integer representing the minimum possible absolute difference between the total difficulties assigned to the two groups.

3
3 1 4

0