Java DFS solution, beats 98% submissions


  • 0
    T
    boolean[] taken;
    public boolean makesquare(int[] nums) {
        float sum = 0;
        for(int i : nums)
            sum+=i;
        sum /= 4;
        if((sum-(int)sum)!=0 || sum == 0){
            return false;
        }
        else{
            Arrays.sort(nums);
            //in descending order. We need to first find the "partners" of the biggest value, because small values are more flexible.
            for(int i = 0; i < nums.length/2; i++){
                int hold = nums[i];
                nums[i] = nums[nums.length-1-i];
                nums[nums.length-1-i] = hold;
            }
            //use one array of labels to check whether i-th match has been used or not.
            taken = new boolean[nums.length];
            Arrays.fill(taken, false);
            for(int i = 0; i < nums.length; i++){
                if(!taken[i]){
                    taken[i] = true;
                    int left = (int)sum-nums[i];
                    if(left < 0){
                        return false;
                    }
                    else if(left == 0){
                        continue;
                    }
                    else{
                        if(!checkNext(left, nums, i)){
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    }
    
    //this part is DFS
    public boolean checkNext(int left, int[] nums, int i){
        for(int j = i+1; j < nums.length; j++){
            if(taken[j] == false){
                int hold = left-nums[j];
                if(hold == 0){
                    taken[j] = true;
                    return true;
                }
                else if(hold > 0){
                    taken[j] = true;
                    if(checkNext(hold, nums, j)) {
                        return true;
                    }
                    else{
                        //if we can't find a suitable solution from current node, then the program will go to the next node and mark this as untaken.
                        taken[j] = false;
                    }
                }
                else {
                    continue;
                }
            }
        }
        return false;
    }

Log in to reply
 

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