#187MediumDynamic Programming· Subset Sum (0/1 Knapsack)

Split Shifts Evenly

A clinic has a list of tasks for the weekend, and each task takes a whole number of minutes (given in `minutes`). The manager wants to divide **all** tasks between two nurses so that both end up with exactly the same total working time. A task cannot be split, and every task must be given to exactly one of the two nurses. Return `true` if such a division exists, otherwise `false`.

Input format

`minutes`: an array of positive integers.

Output format

`true` if the tasks can be divided into two groups with equal total minutes, otherwise `false`.

Examples

Input: minutes = [1, 5, 11, 5]

Output: true

The total is 22. One nurse takes 11 and the other takes 1 + 5 + 5 = 11.

Input: minutes = [1, 2, 3, 5]

Output: false

The total is 11, which is odd, so an equal split is impossible.

Input: minutes = [3, 3, 3, 4, 5]

Output: true

The total is 18; the subset 4 + 5 = 9 (and the rest 3 + 3 + 3 = 9) works.

Constraints

1 <= minutes.length <= 200
1 <= minutes[i] <= 100

#dynamic-programming
#knapsack
#subset-sum
#bitset