The problem requires determining if an array can be partitioned into two subsets with equal
sums.
We use a
dynamic programming
to solve this.
First, we
calculate the total sum
of the array.
If the sum is odd, partitioning is impossible.
If the sum is even, the problem reduces to
finding a subset whose
sum equals half of the total sum.
We create a
2D array 't'
where
t[i][j]
represents whether a subset of the first
'i'
elements can sum up to
'j'.
We fill this table by either
including or excluding
each element, ensuring we build the solution incrementally.
class Solution { public boolean canPartition(int[] nums) { int sum=0; int noOfElements = nums.length; for(int i=0;i<noOfElements;i++){ sum += nums[i]; } if(sum%2!=0) return false; int x = sum/2; int[][] t = new int[noOfElements+1][x+1]; // Column Initialization for(int i=0;i<=x;i++){ t[0][i] = 0; } // Row Initialisation for(int i=0;i<=noOfElements;i++){ t[i][0] = 1; } for(int i=1;i<=noOfElements;i++){ for(int j=1;j<=x;j++){ if(nums[i-1]>j) t[i][j] = t[i-1][j]; else t[i][j] = t[i-1][j] | t[i-1][j-nums[i-1]]; } } if(t[noOfElements][x]==1) return true; else return false; } }
The algorithm iterates through each element and each possible sum value, resulting in a time complexity of O(n * sum), where n is the number of elements and sum is half the total sum.
The algorithm uses a 2D array of size (n+1) x (sum+1) to store intermediate results.