[Java] Easy to Understand, beats 99.96% No DP method.


  • 0
    M

    The idea is pretty simple.
    sort the array first
    sum all the element, if the sum is not an even number, return false
    Starts from the end,
    tmp is to record the temp sum of chosen elements
    if tmp == sum/2 return true
    if tmp > sum/2 deduct the recently added element, move the index to the left, since the element in the left position is smaller.

    public boolean canPartition(int[] nums) {
            Arrays.sort(nums);
    	int sum = 0;
            for(int i =0;i<nums.length;i++)
            {
                sum += nums[i];
            }
            if(sum%2!= 0)
                return false;
            sum = sum/2;
    
            for(int i = nums.length-1;i>0;i--)
            {
                  int tmp = nums[i];
                  if(tmp>sum)
                    return false;
                  if(tmp == sum)
            	return true;
                  int index = i-1;
                  while(index>=0)
                  {
            	  tmp+=nums[index];
            	  if(tmp>sum)
            	       tmp=tmp-nums[index];
            	  if(tmp<sum)
            		index--;
            	   else
            		return true;
            	}
            }
            return false;
        }
    

  • 0
    M

    Actually you don't even need to sort first...


Log in to reply
 

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