问题描述

给定一组雨花石的重量，要求将这些石头分成两组，使得两组的重量相等。如果可以实现这样的分组， 输出所需的最小石头数量；如果无法均分，则输出 $-1$。

解题思路

1. 计算总重量

首先计算所有雨花石的总重量 sum_m。

2. 奇偶性检查

题目内容

MELON有一堆精美的雨花石（数量为 $n$，重量各异），准备送给 S 和 W 。

MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。

输入描述

第 $1$ 行输入为雨花石个数：$n$ ， $0 < n < 31$ 。

第 $2$ 行输入为空格分割的各雨花石重量：$m[0] m[1] ….. m[n - 1]$， $0 < m[k] < 1001$。

不需要考虑异常输入的情况。

输出描述

如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等；

如果不能均分，则输出 $-1$ 。

样例1

输入

4
1 1 2 2

输出

2

说明

输入第一行代表共 $4$ 颗雨花石，

第二行代表 $4$ 颗雨花石重量分别为 $1$、$1$、$2$ 、$2$ 。

均分时只能分别为 $1,2$，需要拿出重量为 $1$ 和 $2$ 的两块雨花石，所以输出 $2$

样例2

输入

10
1 1 1 1 1 9 8 3 7 10

输出

3

说明

输入第一行代表共 $10$ 颗雨花石，

第二行代表 $4$ 颗雨花石重量分别为$1、1、1、1、1、9、8、3、7、10$ 。

均分时可以 $1,1,1,1,1,9,7$ 和 $10,8,3$ ，也可以 $1,1,1,1,9,8$ 和 $10,7,3,1$ ，或者其他均分方式，但第一种只需要拿出重量为 $10,8,3$ 的 $3$ 块雨花石，第二种需要拿出 $4$ 块，所以输出 $3$ (块数最少)。