1、前言

题目描述

2、思路

3、代码

class Solution {
    public boolean makesquare(int[] matchsticks) {
        int total = 0;
        for (int num : matchsticks) {
            total += num;
        }
        if(total == 0 || total % 4 != 0){
            return false;
        }
        Arrays.sort(matchsticks);
        return backTrack(matchsticks, 0, total / 4, new int[4]);
    }

    private boolean backTrack(int[] nums, int index, int target, int[] size){
        if(index == nums.length){
            if(size[0] == size[1] && size[1] == size[2] && size[2] == size[3]){
                return true;
            }
            return false;
        }

        for(int i = 0; i < size.length; i++){
            if(size[i] + nums[index] > target){
                continue;
            }
            size[i] += nums[index];
            if(backTrack(nums, index + 1, target, size)){
                return true;
            }
            size[i] -= nums[index];
        }
        return false;
    }
}