题目

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

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

示例 1:

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

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

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

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

给定的火柴长度和在 0 到 10^9之间。
火柴数组的长度不超过15。

分析

首先判断什么情况下不能形成正方形。什么情况可以。
如果边数少于4跟边数不是4的倍数。肯定不能形成正方形

首先我们一边一边放火材。如果超过边长的话，就回溯。一直到每个边都刚好摆成正方形
就无脑遍历。

代码

class Solution {
    public boolean makesquare(int[] nums) {
        //如果边少于4不能形成正方形
         if (null == nums || nums.length<4){
                return false;
            }
            int account = 0 ;
            for (int temp:nums) {
                account += temp;
            }
        //变数总和不是4的倍数不能成为正方形
            if (account%4!=0){
                return false;
            }
            //冒泡排序 降序
            for (int k = 0; k < nums.length - 1; k++) {
                for (int j = k + 1; j < nums.length; j++) {
                    if (nums[k] < nums[j]) {
                        int temp = nums[k];
                        nums[k] = nums[j];
                        nums[j] = temp;
                    }
                }
            }
            int sideLength = account/4;
            for (int i:nums) {
                //如果有一边大于边长。不能形成正方形
                if (i>sideLength){
                    return false;
                }
            }
        //四边
            int [] sides = new int[4];

            boolean search = search(0, sides, nums, sideLength);

            return search;
    }
    private static boolean search(int pos,int[] sides,int[] nums,int sideLength) {
            //遍历完成后判断每一边是否都相等
            if(pos >= nums.length){
                return  sides[0] == sideLength && sides[1] == sideLength
                        && sides[2] == sideLength && sides[3] == sideLength;
            }

            for (int i = 0; i < sides.length; i++) {
                if (sides[i]+nums[pos]>sideLength){
                    continue;
                }
                sides[i] += nums[pos];

            
                if (search(pos+1,sides,nums,sideLength)){
                    return true;
                };
                //回溯
                sides[i] = sides[i]-nums[pos];
            }



            return false;
        }
}

结果

image.png