LeetCode Hot 100 P416 Partition Equal Subset Sum

---

Timeline

Timeline

2026-03-21

init

Dynamic Programming

---

Problem:

P416 Partition Equal Subset Sum

https://leetcode.cn/problems/partition-equal-subset-sum/?envType=study-plan-v2&envId=top-100-liked

Sum the array, then divide the sum by 2, transforming it into finding a subset of the array whose sum is half of the total, which is a 0-1 knapsack problem.

dp[i][j] indicates whether there exists a selection scheme such that the sum of selected positive integers equals j, when selecting some positive integers (possibly zero) from the index range [0, i] of the array. Initially, all elements in dp are false.

Initialization:

• If no positive integer is selected, the sum of selected positive integers is 0. Therefore, for all 0 ≤ i < n, dp[i][0] = true.
• When i == 0, only one positive integer nums[0] can be selected, so dp[0][nums[0]] = true.

State transition:

• dp[i][j] = dp[i−1][j] ∣ dp[i−1][j−nums[i]](j >= nums[i])
• dp[i][j] = dp[i-1][j](j < nums[i])

#include <vector>
using std::vector;

class Solution {
    public:
        bool canPartition(vector<int> &nums)
        {
                int i, j, n = nums.size();
                int sum = 0, target;

                for (i = 0; i < n; i++)
                        sum += nums[i];

                if (sum % 2 != 0) // Odd
                        return false;

                target = sum / 2;

                for (i = 0; i < n; i++) { // There is a number that exceeds half of the total sum.
                        if (nums[0] > target)
                                return false;
                }

                // 0-1 knapsack problem
                // dp[i][j] represents selecting some positive integers (possibly zero) from the index range [0, i] of the array
                // whether there exists a selection scheme such that the sum of selected positive integers equals j. Initially, all elements in dp are false.
                vector<vector<bool> > dp(n, vector<bool>(target + 1, false));

                // If no positive integer is selected, the sum of selected positive integers is 0. Therefore, for all 0 ≤ i < n, dp[i][0] = true.
                for (i = 0; i < n; i++)
                        dp[i][0] = true;
                // When i == 0, only one positive integer nums[0] can be selected, so dp[0][nums[0]] = true.
                dp[0][nums[0]] = true;

                // dp[i][j] = dp[i−1][j] ∣ dp[i−1][j−nums[i]] (j >= nums[i])
                // dp[i][j] = dp[i-1][j] (j < nums[i])
                for (i = 1; i < n; i++) {
                        for (j = 1; j <= target; j++) {
                                if (j >= nums[i])
                                        dp[i][j] = dp[i - 1][j] | dp[i - 1][j - nums[i]];
                                else
                                        dp[i][j] = dp[i - 1][j];
                        }
                }

                return dp[n - 1][target];
        }
};