Loading problems...
TL;DR: This problem reduces to the 0/1 Knapsack problem where we determine if a subset of numbers exists that sums to exactly half of the total array sum.
The Partition Equal Subset Sum problem asks us to determine if a given integer array nums can be split into two separate subsets such that the sum of elements in both subsets is identical. Mathematically, this implies that the sum of one subset must equal exactly total_sum / 2. If the total sum of the array is odd, it is mathematically impossible to partition it into two equal integer sums, allowing for an immediate return of false.
This is a classic variation of the subset sum problem and a popular interview question. The optimal LeetCode 416 solution utilizes Dynamic Programming to solve the problem efficiently within the given constraints.
The naive approach involves exploring every possible subset of the array to see if its sum equals total_sum / 2. This is typically achieved using recursion. For every element in the array, we have two choices:
We recursively branch out until we either reach the target sum or run out of elements.
Pseudo-code:
textfunction canPartition(index, currentSum, target): if currentSum == target: return true if currentSum > target or index >= length: return false return canPartition(index + 1, currentSum + nums[index], target) OR canPartition(index + 1, currentSum, target)
Complexity Analysis:
The time complexity of this approach is , where is the number of elements in nums. Given the constraint , is an astronomically large number. This approach will inevitably result in a Time Limit Exceeded (TLE) error because it repeatedly recalculates the same subproblems (e.g., reaching the same remaining sum with the same remaining elements index) without memoization.
The key intuition is to shift from asking "What is the subset?" to "Is the sum achievable?".
We first calculate the total sum of the array. If the sum is odd, we return false immediately. If even, our target becomes target = total_sum / 2.
We can maintain a boolean state for every possible sum from 0 up to target. Let dp[i] be true if a sum of i can be formed using a subset of the numbers processed so far.
dp[0] is always true because a sum of 0 is achieved by selecting no elements.num, for every sum j that was previously achievable (dp[j] == true), the sum j + num becomes achievable.Space Optimization (1D Array):
A naive DP approach might use a 2D table dp[index][sum]. However, notice that to calculate reachability for the current number, we only need the reachability states from the previous step. This allows us to compress the state into a single 1D boolean array.
The Crucial Constraint: When using a 1D array, we must iterate through the possible sums backwards (from target down to num). If we iterate forwards, we might use the same number multiple times for the same target sum (e.g., using a 5 to make sum 5, and then using that new sum 5 to make sum 10 in the same iteration). Iterating backwards ensures we only build new sums based on sums achievable before considering the current number.
Visual Description:
Imagine a boolean array of length target + 1, initialized to all false except index 0. This array represents the "reachability" of sums.
5, we scan the array. We find index 0 is true, so we mark index 0 + 5 = 5 as true.3, we scan again. We see 5 is true, so 5 + 3 = 8 becomes true. We see 0 is true, so 0 + 3 = 3 becomes true.
nums.false. Otherwise, calculate target = sum / 2.dp of size target + 1. Set dp[0] = true and all others to false.num in nums.j from target down to num.
dp[j] = dp[j] || dp[j - num].j if we could already form sum j (without this number) OR if we could form sum j - num (and then add this number)."dp[target] becomes true during the process, we can return true immediately.dp[target].Consider nums = [1, 5, 11, 5].
Total Sum = 22. Target = 11.
dp array size 12. dp[0] = true.
Process num = 1:
j from 11 down to 1.dp[1] = dp[1] || dp[0]. Since dp[0] is true, dp[1] becomes true.{0, 1}.Process num = 5:
j from 11 down to 5.dp[6] = dp[6] || dp[1]. dp[1] is true, so dp[6] becomes true.dp[5] = dp[5] || dp[0]. dp[0] is true, so dp[5] becomes true.{0, 1, 5, 6}.Process num = 11:
j from 11 down to 11.dp[11] = dp[11] || dp[0]. dp[0] is true, so dp[11] becomes true.The algorithm is correct based on the principle of mathematical induction applied to the set of reachable sums.
i (processing nums[i]), dp[s] is true if and only if the sum s can be formed using a subset of the previous 0...i-1 elements.dp[0] is correctly set to true.x, a new sum s is possible if s was already possible (don't include x) OR if s - x was possible (include x). The transition dp[j] = dp[j] || dp[j - num] captures exactly these two possibilities.dp[target] reflects whether the target sum is achievable using any combination of the input numbers.cpp#include <vector> #include <numeric> class Solution { public: bool canPartition(std::vector<int>& nums) { int sum = std::accumulate(nums.begin(), nums.end(), 0); // If sum is odd, we cannot split it into two equal integers if (sum % 2 != 0) { return false; } int target = sum / 2; // dp[i] will be true if sum 'i' can be formed by a subset of nums std::vector<bool> dp(target + 1, false); dp[0] = true; for (int num : nums) { // Iterate backwards to avoid using the same number multiple times // for the same sum in a single iteration for (int j = target; j >= num; --j) { if (dp[j - num]) { dp[j] = true; } } } return dp[target]; } };
javaclass Solution { public boolean canPartition(int[] nums) { int sum = 0; for (int num : nums) { sum += num; } // If sum is odd, we cannot split it into two equal integers if (sum % 2 != 0) { return false; } int target = sum / 2; boolean[] dp = new boolean[target + 1]; dp[0] = true; // Base case: sum 0 is always possible for (int num : nums) { // Iterate backwards to ensure each number is used only once per subset for (int j = target; j >= num; j--) { if (dp[j - num]) { dp[j] = true; } } } return dp[target]; } }
pythonclass Solution: def canPartition(self, nums: List[int]) -> bool: total_sum = sum(nums) # If sum is odd, we cannot split it into two equal integers if total_sum % 2 != 0: return False target = total_sum // 2 # dp[i] is True if sum i is achievable dp = [False] * (target + 1) dp[0] = True for num in nums: # Iterate backwards from target to num for j in range(target, num - 1, -1): if dp[j - num]: dp[j] = True return dp[target]
Time Complexity:
nums.total_sum / 2).Space Complexity:
The DP - 1D Array (0/1 Knapsack Subset Sum Style) pattern is highly reusable. Understanding this solution provides the foundation for:
target is equivalent to partitioning the array into two subsets (positive) and (negative) such that .Why does the naive solution TLE?
(index, current_sum) states repeatedly.Why must we iterate backwards in the inner loop?
j from num to target (forward) while using a 1D array.dp[j] might use the updated value of dp[j-num] that already included the current number. This effectively allows using the current number multiple times (Unbounded Knapsack) instead of just once (0/1 Knapsack).true for impossible cases (e.g., nums=[2], target=4 returns true).Why return false if the total sum is odd?
false anyway, skipping this check misses an optimization that instantly solves 50% of impossible cases.