My C Solution using DFS


  • 0
    1
    bool makesquare(int* nums, int numsSize) {
        void quicksort(int* nums,int numsSize);
        bool dfs(int* nums,int numsSize,int* sums,int index,int target);
        int sums[4]={0};
        int i,sum=0;
        
        for(i=0;i<numsSize;i++) sum+=nums[i];
    	if(sum%4 || numsSize<4) return false;
    	for(i=0;i<numsSize;i++)
    	    if(nums[i]>sum/4) return false;
    	quicksort(nums,numsSize);
        return dfs(nums,numsSize,sums,0,sum/4);
    }
    bool dfs(int* nums,int numsSize,int* sums,int index,int target){
    	int i=0;
    	if(index==numsSize)
    		if(sums[0]==target&&sums[1]==target&&sums[2]==target&&sums[3]==target) 
    			return true;
    		else return false;
    	for(i=0;i<4;i++){
    		if(sums[i]+nums[index]<=target) {
    		    sums[i]+=nums[index];
    		    if(dfs(nums,numsSize,sums,index+1,target)) return true;
    		    sums[i]-=nums[index];
    		}
    	}
    	return false;
    
    }
    void quicksort(int *nums,int numsSize){
    	int i=0,j=numsSize-1;
    	int key=nums[0];
    	if(numsSize>1){
    		while(i!=j){
    			for(;i<j;j--)
    				if(nums[j]>key)
    				{	
    					nums[i]=nums[j];
    					break;
    				}
    			for(;i<j;i++)
    				if(nums[i]<key)
    				{	nums[j]=nums[i];
    				    break;
    				}
    			nums[i]=key;
    		}
    		quicksort(nums,i);
    		quicksort(nums+i+1,numsSize-i-1);
    	}
    }
    

Log in to reply
 

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