火柴拼正方形

题目要求

还记得童话《卖火柴的小女孩》吗？现在，你知道小女孩有多少根火柴，请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴，可以把火柴连接起来，并且每根火柴都要用到。

输入为小女孩拥有火柴的数目，每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

示例 1:

输入: [1,1,2,2,2]
输出: true

解释: 能拼成一个边长为2的正方形，每边两根火柴。

示例 2:

输入: [3,3,3,3,4]
输出: false

解释: 不能用所有火柴拼成一个正方形。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/matchsticks-to-square
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

回溯算法+贪心策略

首先我们判断数组元素的和是不是4的倍数，如果不是的话一定返回false。由于火柴不能折断，数组中某一元素大于正方形的边长（数组内元素和/4），那么也将返回false。

接下来我们使用回溯法来判断能否拼成正方形。这道题里面的回溯指的是把火柴放进不同的边里，这就相当于将火柴放入大小为4的数组某一维度中去。直到全部的火柴处理完为止。在处理过程中，如果摸一个边的大小已经超过了正方形的边长，就进行剪枝操作。

贪心算法在题目中应用于从大到小处理，速度会快很多。

public class Solution1 {
    public boolean makesquare(int[] nums) {
        int sum = 0;
        for(int num : nums)
            sum += num;
        if(sum == 0 || sum % 4 != 0)
            return false;
        int target = sum / 4;

        for(int num : nums)
            if(num > target)
                return false;
        //从大到小的回溯，效率更高
        Arrays.sort(nums);
        backtrack(nums.length - 1, nums, target, new int[4]);
        return ans;

    }
    boolean ans = false;
    void backtrack(int cur, int[] nums, int target, int[] temp) {
        if(ans) return;
        if(cur == -1) {
            for(int num : temp)
                if(num != target)
                    return;
            ans = true;
            return;
        }
        for(int i = 0; i < temp.length; i++) {
            int last = temp[i];
            temp[i] += nums[cur];
            if(temp[i] <= target)
                backtrack(cur - 1, nums, target, temp);
            temp[i] = last;
        }
    }
}