Problem Informations

Problem Index: 416
Problem Link: Partition Equal Subset Sum
Topics: Array, Dynamic Programming

Problem Description

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 \leq \text{nums.length} \leq 200$
$1 \leq \text{nums}[i] \leq 100$

Intuition

The problem at hand is a classic example of the “Partition Problem,” which is a well-known problem in computer science. The main goal is to determine if it’s possible to split a given list of integers into two subsets where the sum of the elements in each subset is equal. The challenge here arises from the need to ensure that these subsets have equal sums, rather than just any division of numbers.

The key observation is that if the total sum of the array is an odd number, it is impossible to partition it into two equal integer subsets. Thus, any feasible solution requires the total sum to be even, allowing us to aim for a target sum of half the total for each subset.

Approach

To solve the problem, we utilize a dynamic programming approach with memoization, which optimizes the recursion by storing the intermediate results of subproblems.

Initial Setup:
- Calculate the total sum of the array. If it is odd, return false immediately as it is not possible to split an odd sum equally into two subsets.
- Set target to half of the total sum. The objective now is to determine if there is a subset with a sum equal to target.
Dynamic Programming Table:
- Initialize a 2D vector dp where dp[i][j] will store an optional boolean that indicates if a subset sum j can be achieved using the first i elements of nums.
Recursive Checking with Memoization:
- Begin the recursive process with the first element (idx = 0) and the calculated target.
- Base Cases:
  - If the current index exceeds the length of nums, return false since no further elements are available for consideration.
  - If the target is reached (target == 0), return true as an equal partition subset is found.
  - If the result for dp[idx][target] has already been computed, return its value to avoid redundant calculations.
Recursive Exploration:
- Include Current Element: Check if including the current element in the subset (i.e., target - nums[idx]) still allows reaching the target by recursively checking canPartition(nums, idx + 1, target - nums[idx]).
- Exclude Current Element: If including the current element doesn’t lead to a solution, attempt to exclude it by checking canPartition(nums, idx + 1, target).
Memoization:
- Store the result of each recursive call in dp[idx][target] to prevent duplicated work and ensure efficiency.

The combination of these steps ensures that each possibility is explored efficiently while storing and reusing previously computed outcomes, thus reducing the computational complexity from exponential to polynomial time.

Code

C++

class Solution {
public:
    // Declare a 2D vector to use as memoization for storing intermediate results
    vector<vector<optional<bool>>> dp;

    bool canPartition(vector<int>& nums, int idx = -1, int target = -1) {
        // Initial call setup
        if (idx == -1) {
            // Calculate total sum of array elements
            target = accumulate(nums.begin(), nums.end(), 0);

            // If the total sum is odd, partitioning into equal subsets is impossible
            if (target & 1) return false;

            // The desired sum for each subset is half the total sum
            target /= 2;

            // Clear and resize the dp vector for current nums size and target sum
            dp.clear();
            dp.resize(nums.size(), vector<optional<bool>>(target + 1, nullopt));

            // Start the recursive search from index 0
            return canPartition(nums, 0, target);
        } else {
            // Base case: all elements are considered, return false if we didn't achieve the target
            if (idx >= nums.size()) return false;

            // If this subproblem has already been solved, return the stored result
            if (dp[idx][target].has_value()) return dp[idx][target].value();

            // If the target sum is zero, we have successfully partitioned into two equal subsets
            if (target == 0) return (dp[idx][target] = true).value();

            // Recursive case: try including the current number in the subset and recurse
            // If including the current number at index `idx` still allows a valid partition
            if (target - nums[idx] >= 0 && canPartition(nums, idx + 1, target - nums[idx])) {
                return (dp[idx][target] = true).value();
            }

            // Recursive case: try excluding the current number and recurse
            return (dp[idx][target] = canPartition(nums, idx + 1, target)).value();
        }
    }
};

Python

class Solution:
    # Declare a 2D list to use as memoization for storing intermediate results
    dp = []

    def canPartition(self, nums, idx=-1, target=-1):
        # Initial call setup
        if idx == -1:
            # Calculate total sum of array elements
            target = sum(nums)

            # If the total sum is odd, partitioning into equal subsets is impossible
            if target & 1:
                return False

            # The desired sum for each subset is half the total sum
            target //= 2

            # Clear and resize the dp list for current nums size and target sum
            self.dp = [[None] * (target + 1) for _ in range(len(nums))]

            # Start the recursive search from index 0
            return self.canPartition(nums, 0, target)
        else:
            # Base case: all elements are considered, return false if we didn't achieve the target
            if idx >= len(nums):
                return False

            # If this subproblem has already been solved, return the stored result
            if self.dp[idx][target] is not None:
                return self.dp[idx][target]

            # If the target sum is zero, we have successfully partitioned into two equal subsets
            if target == 0:
                self.dp[idx][target] = True
                return True

            # Recursive case: try including the current number in the subset and recurse
            # If including the current number at index `idx` still allows a valid partition
            if target - nums[idx] >= 0 and self.canPartition(nums, idx + 1, target - nums[idx]):
                self.dp[idx][target] = True
                return True

            # Recursive case: try excluding the current number and recurse
            self.dp[idx][target] = self.canPartition(nums, idx + 1, target)
            return self.dp[idx][target]

Complexity

Time complexity: The time complexity of the given algorithm is $O(n \cdot m)$, where $n$ is the number of elements in the input array nums, and $m$ is the target sum that is half of the total sum of the array. In the worst case, we explore each subset possibility for every element up to the target sum. The use of memoization reduces redundant calculations.
Space complexity: The space complexity is $O(n \cdot m)$ due to the use of a 2D vector dp which stores intermediate results for n elements and possible sums up to m. Additionally, the call stack for recursion can grow up to $O(n)$, but this does not affect the asymptotic space complexity when accounting for the dp vector.

CS Note
中

Leetcode 416. Partition Equal Subset Sum