Pseudo-code:

text
function 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 $O(2^n)$, where $n$ is the number of elements in nums. Given the constraint $n \le 200$, $2^{200}$ 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.

Core Insight for Partition Equal Subset Sum

The key intuition is to shift from asking "What is the subset?" to "Is the sum $S$ 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.

1. Base Case: dp[0] is always true because a sum of 0 is achieved by selecting no elements.
2. Transition: When considering a new number 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.

• Initially, only index 0 is reachable.
• When we process a number, say 5, we scan the array. We find index 0 is true, so we mark index 0 + 5 = 5 as true.
• When we process the next number, say 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.
• The array effectively accumulates all possible subset sums.

Algorithm Strategy: DP - 1D Array (0/1 Knapsack Subset Sum Style)

1. Calculate Sum: Compute the sum of all elements in nums.
2. Check Parity: If the sum is odd, return false. Otherwise, calculate target = sum / 2.
3. Initialize DP Array: Create a boolean array dp of size target + 1. Set dp[0] = true and all others to false.
4. Iterate Numbers: Loop through each integer num in nums.
5. Iterate Sums (Backwards): Inside the loop, iterate a variable j from target down to num.
   • Update rule: dp[j] = dp[j] || dp[j - num].
   • This means: "We can form sum j if we could already form sum j (without this number) OR if we could form sum j - num (and then add this number)."
6. Early Exit (Optional): If dp[target] becomes true during the process, we can return true immediately.
7. Final Result: Return dp[target].

Execution Flow

Consider nums = [1, 5, 11, 5]. Total Sum = 22. Target = 11. dp array size 12. dp[0] = true.

1. Process num = 1:

   • Iterate j from 11 down to 1.
   • dp[1] = dp[1] || dp[0]. Since dp[0] is true, dp[1] becomes true.
   • Reachable sums: {0, 1}.

2. Process num = 5:

   • Iterate 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.
   • Reachable sums: {0, 1, 5, 6}.

3. Process num = 11:

   • Iterate j from 11 down to 11.
   • dp[11] = dp[11] || dp[0]. dp[0] is true, so dp[11] becomes true.
   • Target 11 is reached. Return true.

Proof of Correctness

The algorithm is correct based on the principle of mathematical induction applied to the set of reachable sums.

1. Invariant: At the start of iteration 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.
2. Base Case: Before any elements are processed, only sum 0 is possible (empty subset). dp[0] is correctly set to true.
3. Inductive Step: When considering element 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.
4. Termination: After processing all numbers, dp[target] reflects whether the target sum is achievable using any combination of the input numbers.

Reference Implementation

C++ Solution for LeetCode 416

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];
    }
};

Java Solution for LeetCode 416

java
class 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];
    }
}

Python Solution for LeetCode 416

python
class 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]