Partition Equal Subset Sum 2D dp
Description
Leetcode 416. 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.
Example 1:
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].
1
2
3
2
3
Example 2:
Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.
1
2
3
2
3
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 100
1
2
2
Process
1. Consider exceptions
if (nums.size() == 1)
return false;
1
2
2
2. Determine 2D array dp[i][j]
dp[i][j]: with numbers starting from index 0 and ending at i of vector nums, and with the capacity (maximum theoretical sum) being j, the actual maximum sum is dp[i][j].
3. Find the target sum of the two possible identical subsets
//find the sum of all integers in the vector
int sum = 0;
for (int x : nums)
{
sum += x;
}
//if the vector nums cannot be divided into two equal integers, it can not be partitioned
if (sum & 1) //same as (sum % 2)
return false;
int target = sum / 2;
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
4. Determine the size of dp[i][j]
vector<vector<int>> dp(nums.size(), vector<int>(target+1, 0));
1
5. Initialize dp[0][j]
As for the first element, if the capacity is equal to or bigger than the value of the first number, it means the maximum sum is nums[0].
for (int j = 1; j <= target; j++)
{
if (j >= nums[0])
dp[0][j] = nums[0];
}
1
2
3
4
5
2
3
4
5
6. Equation and traversal
When making an example of input nums = [1,2,3,4], the target is (1+2+3+4)/2 = 5. When we try iterating from the start to the end we find some values will be added more than once. So for variable j, we iterate form the end to the start. 
for (int i = 1; i < nums.size(); i++)
{
for (int j = target; j > 0; --j)
{
//if the current number exceeds the capacity
if (nums[i] > j)
dp[i][j] = dp[i - 1][j]; //not adding the current number
//if the current number can be added
else
{
//adding the current number and not adding the current number
dp[i][j] = max(dp[i - 1][j - nums[i]] + nums[i], dp[i - 1][j]);
}
/*if with the target capacity, a sum of the target can be met,
* it means there exists a subset with a sum which is half of the sum of the whole vector
*/
if (j == target && dp[i][j] == target)
return true;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
Solution
#include <vector>
using namespace std;
// @lc code=start
//*dp 2D array
class Solution
{
public:
bool canPartition(vector<int> &nums)
{
//1.make an example
//2.consider exceptions
if (nums.size() == 1)
return false;
int sum = 0;
for (int x : nums)
{
sum += x;
}
//if the vector nums cannot be divided into two equal integers
if (sum & 1) //sum%2==1
return false;
int target = sum / 2;
//3.dp[i][j]: with numbers from vector nums[0,i], and with the capacity (maximum theoretical sum) being j, the maximum sum is dp[i][j]
//4.initialize
//the maximum possible sum is 200*100/2=10000, index 10000 is the 10001st element
vector<vector<int>> dp(nums.size(), vector<int>(target+1, 0));
//find the sum of all integers in the vector
//initialize for the first element, if the capacity is equal to or bigger than the value of the first number, it means the maximum sum is nums[0]
for (int j = 1; j <= target; j++)
{
if (j >= nums[0])
dp[0][j] = nums[0];
}
//5.equation and traversal
for (int i = 1; i < nums.size(); i++)
{
for (int j = 1; j <=target; ++j)
{
//if the current number exceeds the capacity
if (nums[i] > j)
{
dp[i][j] = dp[i - 1][j]; //not adding the current number
}
//if the current number can be added
else
{
dp[i][j] = max(dp[i - 1][j - nums[i]] + nums[i], dp[i - 1][j]); //adding the current number and not adding the current number
}
//if with the target capacity, a sum of the target can be met, it means it is possible to have a subset with a sum which is half of sum of the whole vector
if (j == target && dp[i][j] == target)
return true;
}
}
return false;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62