Solution
Let’s say the sum of all elements in the array is totSum. The array can be partitioned into two equal halves only if totSum is even. Further, there should be a subset having sum = totSum/2. The first part, calculating totSum and imposing the even condition, is easy. How to check whether a subset having sum equal to totSum/2 exists? This can be solved using backtracking where we consider two cases: element i is in subset and element i is not in the subset and then recurse. This will take up lot of time though. Note that we essentially have to find a whether some elements from the input array make up the sum = totSum/2 - this problem is like the 0/1 knapsack problem which is classically solved using a 2D DP (it can also be solved using 1D DP but here I will only mention 2D DP solution). Define a 2D vector dp where dp[i][j] denotes whether sum=j can be formed using input[1..i]. Let’s take an example, let input = [1, 5, 11, 5]. Here, totSum = 22 so we have to find a subset having sum=11. Let us define out 2D array as below:
0 1 2 3 4 5 6 7 8 9 10 11
1 0 0 0 0 0 0 0 0 0 0 0
1: 1 1 0 0 0 0 0 0 0 0 0 0
5: 1 1 0 0 0 1 1 0 0 0 0 0
11: 1 1 0 0 0 1 1 0 0 0 0 1
5: 1 1 0 0 0 1 1 0 0 0 1 1
Here the columns represent sum from 0 to 11 and the rows represent the input elements used. The first row indicates that no input element is used. dp[i][j] = 1 if the specific sum j can be gotten from the first i numbers. If we can pick such a series of numbers from 0-i whose sum is j, dp[i][j] is true (=1), otherwise it is false (=0).
| Transition function: For each number, if we don’t pick it, dp[i][j] = dp[i-1][j], which means if the first i-1 elements has made it to j, dp[i][j] would also make it to j (we can just ignore nums[i-1]). If we pick nums[i-1], dp[i][j] = dp[i-1][j-nums[i-1]], which represents that j is composed of the current value nums[i] and the remaining composed of other previous numbers. Thus, the transition function is dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i-1]]. |
bool canPartition(vector<int>& nums) {
int totSum=0;
for (int i : nums)
totSum+=i;
if (totSum&1 || totSum<2)
return false;
int subsetSum = totSum/2;
vector<vector<bool>> v(nums.size()+1, vector<bool>(subsetSum+1, false));
for (int i=0; i<=nums.size(); i++)
v[i][0] = true;
for (int i=1; i<=nums.size(); i++) {
for (int j=1; j<=subsetSum; j++) {
v[i][j] = v[i-1][j];
if (j-nums[i-1]>=0)
v[i][j]=v[i][j]||v[i-1][j-nums[i-1]];
if (j==subsetSum && v[i][j])
return true;
}
}
return false;
}
Time complexity: O(nm) where n is the size of nums and m is the total sum of the numbers Space complexity: O(nm)