Partition Equal Subset Sum 1D 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

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

1
2
3

Constraints:

1 <= nums.length <= 200
1 <= nums[i] <= 100

1
2

Process

1. Consider exceptions

if (nums.size() == 1)
    return false;

1
2

2. Determine 1D array dp[j]

dp[j]: j denotes the maximum capacity of the subset, dp[j] denotes the actual sum of the subset

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

4. Determine the size of dp[j]

vector<int> dp(target+1, 0);

5. Equation and traversal

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. Example of dynamic programming

for (int i = 0; i < nums.size(); i++)
{
    for (int j = target; j >= nums[i]; j--)
    {
        dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
    }

    if (dp[target] == target)
        return true;
}

1
2
3
4
5
6
7
8
9
10

Solution

#include <vector>
using namespace std;

// @lc code=start
//*dp 1D array
class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        // 1.make an example
        // 2.consider exceptions
        if (nums.size() == 1)
            return false;

        int target = 0;
        for (int x : nums)
        {
            target += x;
        }
        // if the target value cannot be divided into two equal integers
        if (target & 1) // target%2
            return false;
        target /= 2; // sum of the target subsets

        // 3.dp[j]: j denotes the maximum capacity of the subset
        // 3.dp[j]: dp[j] denotes the actual sum of the subset

        // 4.initialise
        vector<int> dp(target + 1, 0);

        // 5.determine order of traversal: from end to front
        for (int i = 0; i < nums.size(); i++)
        {
            for (int j = target; j >= nums[i]; j--)
            {
                dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);
            }

            if (dp[target] == 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

# Partition Equal Subset Sum 1D dp

# Description

# Process

# 1. Consider exceptions

# 2. Determine 1D array dp[j]

# 3. Find the target sum of the two possible identical subsets

# 4. Determine the size of dp[j]

# 5. Equation and traversal

# Solution