Partition Equal Subset Sum

check if partitions having equal sum are present or not
 avatar
Divyansh666
java
2 years ago
1.2 kB
2
Indexable
Never
// Que  Partition Equal Subset Sum

// Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

// Input: nums = [1,5,11,5]
// Output: true
// Explanation: The array can be partitioned as [1, 5, 5] and [11].

//  Link -- https://leetcode.com/problems/partition-equal-subset-sum/



class Solution {
    public boolean canPartition(int[] nums) {
        int sum=0;
        for(int i=0;i<nums.length;i++){
            sum+=nums[i];
        }
        if(sum%2!=0){
            return false;
        }
        
        return help(0,nums,sum/2);
    }
    
    private static boolean help(int currPos, int []arr, int sum){
        if(sum==0){
            return true;
        }
        if(currPos>=arr.length){
            return false;
        }
        
        boolean consider = false;
        if(sum>=arr[currPos]){
             consider = help(currPos+1, arr, sum-arr[currPos]);
        }
       
        boolean notConsider = help(currPos+1, arr, sum);
        
        return consider|| notConsider;
    }
}