Partition Equal Subset Sum (optimised)

Divyansh666
java
2 years ago
1.6 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].

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, new HashMap<String, Boolean>());
}

private static boolean help(int currPos, int []arr, int sum, HashMap<String,Boolean> memo){
if(sum==0){
return true;
}
if(currPos>=arr.length){
return false;
}

String key = Integer.toString(currPos)+"-"+Integer.toString(sum);

if(memo.containsKey(key)){
return memo.get(key);
}

boolean consider = false;
boolean notConsider = false;

if(sum>=arr[currPos]){
consider = help(currPos+1, arr, sum-arr[currPos],memo);
}

if(consider!=true){
notConsider = help(currPos+1, arr, sum,memo);
}

boolean ans =  consider|| notConsider;
memo.put(key,ans);
return memo.get(key);
}
}```