[Data Structure] Woodle Fright Square Stick To Square

Wood stick square square Stick to Square

A integer groupsticksOn behalf of a pile of wooden sticks, the wooden stick cannot be broken, but it can be connected. Every wooden stick is used. Can the given wooden stick be a square.

sticks = [1, 1, 2, 2, 2] OUT: TRUE

Thinking

UseDFS,

First, make a non-decreasing order of array. Calculate all wooden sticks and SUM. If SUM% 4! = 0, the description cannot be metered into a square.

OtherwisedfsReady to find a possible solution. Establish a array arr to save the length of the rest of each side that needs the length of the wooden stick.

There are N wooden sticks, from the longest Nth Woody stick to forward, set if all wooden sticks are finished, ind == – 1, find the correct solution.

Cycle to 4 strips attempt to put into the origin, if Arr [i] <ms [ind], indicating that the wooden stick is longer than the remaining length of this side, can not be placed in Arr [i], looking for the next one i. Otherwise 2 cases will appear,

  1. arr [i] == ms [ind] Wooden stick length is just equal to the remaining length of the i-th side, Arr [i] – = ms [ind], then continuedfsAt this point, MS [IND-1] is to be processed.
  2. arr [I]> MS [IND] The length of the wooden stick is just larger than the remaining length of the i-th side, but if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than if it is greater than it. At this time, MS [0] is the smallest wooden stick, if Arr [I]> = MS [IND] + MS [0] is not met, the Arr [I] is not possible to fill in other wooden sticks with MS [Ind] .

Reduce by 2 abovedfsBranches.

public boolean makesquare(int[] sticks) {        Arrays.sort(sticks);// s to l        int sum =0;        for(int i=0;i<sticks.length;i++){            sum+= sticks[i];        }        if(sum%4!=0){            return false;        }        int[] arr = new int[4];        for(int i=0;i<arr.length;i++){            arr[i]=sum/4;        }        return dfs(sticks.length-1,arr,sticks);    }    public boolean dfs(int ind ,int[] arr,int[] ms){        if(ind==-1){            return true;        }        for(int i = 0;i<4;i++){            if(arr[i]<ms[ind]){                continue;            }            if(arr[i]==ms[ind]||arr[i]>=ms[ind]+ms[0] ){                arr[i]-=ms[ind];                if(dfs(ind-1,arr,ms)){                    return true;                }                arr[i]+=ms[ind];            }        }        return false;    }

Tag

DFS