华为OD机试之MELON的难题（Java源码）

MELON的难题

题目描述
MELON有一堆精美的雨花石(数量为n，重量各异)，准备送给S和W。MELON希望送给俩人的雨花石重量一致，请你设计一个程序，帮MELON确认是否能将雨花石平均分配。

---

输入描述
第1行输入为雨花石个数: n，0<n<31。
第2行输入为空格分割的各雨化石重量: m[0] m[1] … m[n- 1]， 0< m[k] < 1001
不需要考虑异常输入的情况。

---

输出描述
如果可以均分，从当前雨花石中最少拿出几块，可以使两堆的重量相等;如果不能均分，则输出-1。

用例

解析

示例代码

import java.util.Scanner;

//MELON的难题
public class T62 {
	static int avg = 0;//
	static int[] tempNum = null;// 取到的数
	static int minCount = 0;
	static int nums[] = null;
	static int tempIndex[] = null;// 取了哪些索引

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int num = Integer.parseInt(sc.nextLine());
		nums = new int[num];
		int sum = 0;
		for (int i = 0; i < num; i++) {
			nums[i] = sc.nextInt();
			sum += nums[i];
		}
		if (sum % 2 != 0) {
			System.out.println(-1);
			System.exit(0);
		}
		avg = sum / 2;
		tempNum = new int[num];
		tempIndex = new int[num];
		for (int i = 0; i < num; i++) {
			tempIndex[i] = -1;
		}
		minCount = num;
		dfs(0, 0);
		System.out.println(minCount);
	}

	public static void dfs(int p, int count) {
		int tempSum = 0;
		for (int i = 0; i < count; i++) {
			tempSum += tempNum[i];
			if (tempSum == avg) {
				if (minCount > count) {
					minCount = count;
				}
				break;
			}
			if (tempSum > avg) {
				// 超了
				return;
			}
		}
		for (int j = 0; j < nums.length; j++) {
			boolean flag = false;
			for (int k = 0; k <= count; k++) {
				if (tempIndex[k] == j) {
					flag = true;
					break;
				}
			}
			if (!flag) {
				tempNum[count] = nums[j];
				tempIndex[count] = j;
				dfs(p + 1, count + 1);
			}
		}
	}
}

代码运行截图