[473]Matchsticks to Square

leetcode

My Solution

This question is talking about split the array into 4 groups, they equal to each other.

-- sum the array and divide by 4, calculate the length of edge.
-- using dfs solution, to divide each number into 4 group, to check true or false.
-- when divide, check whether each group sum larger than edge.

public class Solution {
    public boolean makesquare(int[] nums) {
        
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        if (sum % 4 != 0 || sum == 0) return false;

        int edge = sum / 4;
        int[] box = new int[4];

        if(helper(nums,box,edge,0)){
            for(int b : box){
                if(b != edge)return false;
            }
            return true;
        }

        return false;

    }

    public boolean helper(int[] nums, int[] box, int edge, int start) {
        if (start == nums.length) return true;

        int n = nums[start];

        for (int i = 0; i < 4; i++) {
            if (box[i] + n <= edge) {
                box[i] += n;
                if (helper(nums, box, edge, start + 1)) return true;
                box[i] -= n;
            }
        }
        return false;
    }


}

optimization

Sort the array in descending order can speed up the dfs.