Java 12ms Recursive Solution, easy to understand


  • 0
    F
    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 == 1)
    		return false;
    	return helper(nums, nums.length - 1, sum / 2);
    
    }
    
    private boolean helper(int[] nums, int index, int target) {
    	if (index < 0)
    		return false;
    	if (nums[index] > target)
    		return false;
    	if (nums[index] == target)
    		return true;
    	target = target - nums[index];
    	
    	for (int i = index - 1; i >= 0; i--) {
    		if (nums[i] == target)
    			return true;
    		if (nums[i] <= target) {
    			boolean temp = helper(nums, i - 1, target - nums[i]);
    			if (temp) {
    				return true;
    			}
    		}
    	}
    	return false;
    }

Log in to reply
 

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