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: bool canPartition(vector<int>& nums) { int sz = nums.size(); int sum = 0; for(int i=0;i<sz;i++) sum += nums[i]; // Below is the required sum for each subset. int requiredSum = sum/2; // Now, problem reduces to tell if it is possible to make a subset whose // sum = requiredSum. If sum is odd, then we can't do parition of the set if(sum%2==1) return false; bool t[sz+1][requiredSum+1]; // If number of elements are zero, then are can't create requiredSum for(int i=0;i<=requiredSum;i++){ t[0][i] = false; } // If sum value = 0 then we can create two empty subset whose sum = 0 for(int i=0;i<=sz;i++){ t[i][0] = true; } for(int i=1;i<=sz;i++){ for(int j=1;j<=requiredSum;j++){ if(nums[i-1]>j) t[i][j] = t[i-1][j]; else // Either select it OR reject it. t[i][j] = t[i-1][j] || t[i-1][j-nums[i-1]]; } } return t[sz][requiredSum]; } };
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.