Java 11ms solution without DP (98.69%)


  • 1
    I
     public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        if (sum % 2 != 0) {
            return false;
        }
        int target = sum / 2;
        Arrays.sort(nums);
        return helper(nums, nums.length - 2, target - nums[nums.length - 1]);
    }
    
    public boolean helper(int[] nums, int idx, int target) {
        if (target == 0) {
            return true;
        } if (target < 0 || idx < 0) {
            return false;
        }
        
        return helper(nums, idx - 1, target - nums[idx]) || helper(nums, idx - 1, target);
    }

  • 0
    This post is deleted!

  • 0

    Smart move! thanks.
    //if the biggest is not the target, then find it in the smaller numbers or find the remainder in the smaller numbers.
    return helper(nums, idx - 1, target - nums[idx]) || helper(nums, idx - 1, target);


Log in to reply
 

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