Partition Equal Subset Sum
check if partitions having equal sum are present or notDivyansh666
java
3 years ago
1.2 kB
6
Indexable
// 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; } }
Editor is loading...