Partition Equal Subset Sum medium

Problem Statement

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.

Steps

1. Calculate the total sum: Find the sum of all elements in the input array nums. If the sum is odd, it's impossible to partition the array into two subsets with equal sums, so return false.

2. Dynamic Programming: Use a boolean array dp of size sum / 2 + 1. dp[i] will be true if there exists a subset of nums whose sum is i, and false otherwise.

3. Initialization: dp[0] is true because an empty subset has a sum of 0.

4. Iteration: Iterate through each number num in nums. For each num, iterate through dp from sum / 2 down to num. If dp[i - num] is true (meaning there's a subset with sum i - num), then dp[i] can be set to true (because adding num to that subset results in a subset with sum i).

5. Result: After iterating through all numbers, dp[sum / 2] will indicate whether there exists a subset with a sum equal to half the total sum. Return dp[sum / 2].

Explanation

The dynamic programming approach cleverly uses a boolean array to track the possibility of achieving different subset sums. By iterating through the numbers and updating the dp array, we efficiently determine whether a subset with half the total sum exists. The backward iteration (from sum/2 down to num) is crucial to avoid double-counting subsets.

Code

#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0) return false; // Odd sum, impossible to partition

        int target = sum / 2;
        std::vector<bool> dp(target + 1, false);
        dp[0] = true; // Empty subset has sum 0

        for (int num : nums) {
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[target];
    }
};

Complexity

• Time Complexity: O(N * S), where N is the number of elements in nums and S is the sum of elements in nums. The nested loops dominate the runtime.
• Space Complexity: O(S), where S is the sum of elements in nums. The dp array requires space proportional to the target sum.