LeetCode 473. Matchsticks to Square

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2016/12/30/LeetCode-473-Matchsticks-to-Square/
访问原文「LeetCode 473. Matchsticks to Square」

题目要求

Remember the story of Little Match Girl? By now, you know exactly what matchsticks the little match girl has, please find out a way you can make one square by using up all those matchsticks. You should not break any stick, but you can link them up, and each matchstick must be used exactly one time.

Your input will be several matchsticks the girl has, represented with their stick length. Your output will either be true or false, to represent whether you could make one square using all the matchsticks the little match girl has.

Example 1:

Input: [1,1,2,2,2]
Output: true

Explanation: You can form a square with length 2, one side of the square came two sticks with length 1.

Example 2:

Input: [3,3,3,3,4]
Output: false

Explanation: You cannot find a way to form a square with all the matchsticks.

Note:

The length sum of the given matchsticks is in the range of 0 to 10^9.
The length of the given matchstick array will not exceed 15.

题意解析

卖火柴的小女孩卖的火柴长短不一（妈呀），问，这些火柴能不能排列一个正方形（我觉得组不成就掰断呗，感觉上和当初的给池子灌水，一边灌一边漏，问什么时候能灌满的没有实际意义的题目一样）。

解法分析

因为咱们的火柴不能掰断，所以首先要做的就是算一下所有火柴的长度和除以4能不能除尽，不能除尽当然不行了。然后排了个序（排序是为了之后在递归的时候剪枝用），看看最长的是不是比正方形的单边长度还要长，长的话也是不行的。

接着我们就要计算有没有合适的火柴组合可以组合成正方形的单边，这个时候要用到递归了。前面我们已经做了排序，递归过程中只要发现了当前的长度和大于单边长度就没有必要再继续遍历下去了。

因为满足组合成正方形单边的组合很多，所以每一次遍历都要把所有组合记录下来，然后在每个组合的基础上再从剩下的火柴中找满足需求的组合。

解题代码

public boolean makesquare(int[] nums) {
	if (null == nums || nums.length <= 0) {
		return false;
	}
	long sum = 0l;
	Arrays.sort(nums);
	List<Integer> allNums = new ArrayList<Integer>();
	for (int num : nums) {
		sum += num;
		allNums.add(num);
	}
	if (sum % 4 != 0) {
		return false;
	}
	int average = (int) sum / 4;
	if (nums[nums.length - 1] > average) {
		return false;
	}
	return makeSquare(allNums, average, 0, 2);
}
private boolean makeSquare(List<Integer> allNums, int average, int step,
		int maxSteps) {
	Set<List<Integer>> numbersList = new HashSet<List<Integer>>();
	findFixNumbers(numbersList, new ArrayList<Integer>(), allNums, 0, 0,
			average);
	if (!numbersList.isEmpty()) {
		if (step == maxSteps) {
			return true;
		}
		for (List<Integer> numbers : numbersList) {
			for (int number : numbers) {
				allNums.remove((Integer) number);
			}
			boolean result = makeSquare(allNums, average, step + 1,
					maxSteps);
			if (result) {
				return true;
			}
			for (int number : numbers) {
				allNums.add((Integer) number);
			}
			Collections.sort(allNums);
		}
	}
	return false;
}
private boolean findFixNumbers(Set<List<Integer>> numbersList,
		List<Integer> numbers, List<Integer> nums, int index, int nowNum,
		int average) {
	if (nowNum == average) {
		return true;
	}
	if (nowNum < average) {
		for (int i = index; i < nums.size(); i++) {
			if (nowNum + nums.get(i) > average) {
				return false;
			}
			numbers.add(nums.get(i));
			if (findFixNumbers(numbersList, numbers, nums, i + 1, nowNum
					+ nums.get(i), average)) {
				numbersList.add(new ArrayList<Integer>(numbers));
			}
			numbers.remove((Integer) nums.get(i));
		}
	}
	return false;
}