416. Partition Equal Subset Sum

https://leetcode.com/problems/partition-equal-subset-sum/

Problem

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].

Example 2:

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

Constraints:

• 1 <= nums.length <= 200

• 1 <= nums[i] <= 100

Solution

1. Knapsack

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (const auto n: nums) sum += n;
        if (sum % 2 != 0) return false;
        const int size = nums.size() + 1, W = sum / 2 + 1;
        int knapsack[size][W];
        for (int w = 0; w < W; ++w) knapsack[0][w] = 0;
        for (int i = 0; i < size; ++i) knapsack[i][0] = 0;
        for (int i = 1; i < size; ++i) {
            for (int w = 1; w < W; ++w) {
                if (nums[i - 1] <= w) {
                    knapsack[i][w] = max(knapsack[i - 1][w], nums[i - 1] + knapsack[i - 1][w - nums[i - 1]]);
                } else {
                    knapsack[i][w] = knapsack[i - 1][w];
                }
            }
        }
        return knapsack[size - 1][W - 1] == W - 1;
    }
};

2. DP

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (const auto n: nums) sum += n;
        if (sum % 2 != 0) return false;
        const int size = nums.size() + 1, S = sum / 2 + 1;
        bool dp[size][S];
        for (int s = 0; s < S; ++s) dp[0][s] = false;
        for (int i = 0; i < size; ++i) dp[i][0] = true;
        for (int i = 1; i < size; ++i) {
            for (int s = 1; s < S; ++s) {
                if (nums[i - 1] > s) {
                    dp[i][s] = false;
                } else {
                    dp[i][s] = dp[i - 1][s] || dp[i - 1][s - nums[i - 1]];
                }
            }
        }
        return dp[size - 1][S - 1];
    }
};

3. Optimized DP

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (const auto n: nums) sum += n;
        if (sum % 2 != 0) return false;
        const int size = nums.size() + 1, S = sum / 2 + 1;
        bool dp[S];
        memset(dp, 0, S);
        dp[0] = true;
        for (int i = 0; i < nums.size(); ++i) {
            for (int s = S - 1; s >= nums[i]; --s) {
                dp[s] = dp[s] || dp[s - nums[i]];
            }
        }
        return dp[S - 1];
    }
};

• #dp

• #knapsack

• #math