416. Partition Equal Subset Sum

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

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

Approach 01:

#include <numeric>
#include <vector>

using namespace std;

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);

        if (totalSum % 2 != 0)
            return false;

        return knapsack(nums, totalSum / 2);
    }

private:
    bool knapsack(const vector<int>& nums, int targetSum) {
        int n = nums.size();
        vector<vector<bool>> dp(n + 1, vector<bool>(targetSum + 1, false));
        dp[0][0] = true;

        for (int i = 1; i <= n; ++i) {
            int currentNum = nums[i - 1];
            for (int currSum = 0; currSum <= targetSum; ++currSum) {
                if (currSum < currentNum)
                    dp[i][currSum] = dp[i - 1][currSum];
                else
                    dp[i][currSum] = dp[i - 1][currSum] || dp[i - 1][currSum - currentNum];
            }
        }

        return dp[n][targetSum];
    }
};

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        totalSum = sum(nums)
        if totalSum % 2 != 0:
            return False
        return self.knapsack(nums, totalSum // 2)

    def knapsack(self, nums: List[int], targetSum: int) -> bool:
        n = len(nums)
        dp = [[False] * (targetSum + 1) for _ in range(n + 1)]
        dp[0][0] = True

        for i in range(1, n + 1):
            currentNum = nums[i - 1]
            for currSum in range(targetSum + 1):
                if currSum < currentNum:
                    dp[i][currSum] = dp[i - 1][currSum]
                else:
                    dp[i][currSum] = dp[i - 1][currSum] or dp[i - 1][currSum - currentNum]

        return dp[n][targetSum]

Time Complexity:

• Knapsack DP Table Filling:

  There are \( n \) items and \( \text{targetSum} \) possible sums. For each item, we iterate through all possible sums, which results in \( O(n \times \text{targetSum}) \) time.

• Sum Calculation:

  The call to accumulate() takes \( O(n) \) time.

• Total Time Complexity:

  \( O(n \times \text{targetSum}) \), where \( n \) is the number of elements and \( \text{targetSum} = \frac{\text{totalSum}}{2} \).

Space Complexity:

• DP Table:

  We use a 2D DP table of size \( (n + 1) \times (\text{targetSum} + 1) \), leading to \( O(n \times \text{targetSum}) \) space.

• Total Space Complexity:

  \( O(n \times \text{targetSum}) \)