One more approach Using a boolean array (22ms)


  • 0
    C

    In this solution, a different way to iterate over the elements is given. We keep track of how many sides of a square are formed and what elements are traversed. When a new side is formed, we will again start iterating from zeroth element. I think, this solution avoids the same combinations being selected again, which is the case in other solutions using an sum array of size 4. Repeating again from zeroth element looks like a bad approach but we are doing that only when a side is formed.

    For example, given [2,1,1,2,3,3,4], we know subset [2,1,1] is a bad choice but this will be chosen 4 times in solutions which use sum array. This solution avoids that.

    public class Solution {
        public boolean makesquare(int[] nums) {
            int sum = 0, max = 0;
            for(int i = 0; i < nums.length; i++) {
                if(nums[i] < 0) return false;
                sum += nums[i];
                max = Math.max(max, nums[i]);
            }
            if(sum % 4 != 0 || max > sum/4) return false;
            Arrays.sort(nums);
            return helper(nums, new boolean[nums.length], sum/4, 0, 0, 0);
        }
        
        boolean helper(int nums[], boolean bool[], int side, int no_formed, int index, int curr_sum) {
            
            if(curr_sum == side && no_formed == 2) return true;
            if(index >= nums.length || curr_sum > side) return false;
            
            // when a new side formed
            if(curr_sum == side) {
                no_formed++;
                index = 0;
                curr_sum = 0;
            }
            
            for(int i = index; i < nums.length; i++) {
                if(!bool[i]) {
                    if(curr_sum + nums[i] > side) return false;
                    bool[i] = true;
                    if(helper(nums, bool, side, no_formed, i+1, curr_sum + nums[i])) return true;
                    bool[i] = false;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.