Problem Summary

You are given an integer array nums.
Your task is to determine whether the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be split into [1,5,5] and [11].

Input: nums = [1,2,3,5]
Output: false
Explanation: Equal partition is not possible.

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100
• Expected complexity: O(n × sum(nums)/2)

---

Core Insight

If the total sum of the array is S, then both subsets must sum to:

target = S / 2

This is only possible if S is even.

So the problem becomes:
Can we find a subset of nums that sums exactly to target?

This is a classic 0/1 Knapsack problem.

---

Approach (Simple English)

We reduce the problem to checking whether a subset sum exists that equals target.

Key Idea

Use Dynamic Programming to determine which sums are achievable.

Define a boolean DP array:

dp[s] = true if some subset of nums can achieve sum = s

We try to fill dp up to target.

Why This Works

If dp[target] becomes true, then the array can be partitioned into two equal subsets.

Steps

1. Compute the total sum.
2. If sum is odd → return false.
3. Set target = sum / 2.
4. Initialize dp array of size target+1:
   • dp[0] = true (empty subset)
5. For each num in nums:
   • Update dp in reverse from target down to num: if dp[s - num] is true → dp[s] becomes true
6. Final answer is dp[target].

This is an optimized knapsack solution.

Time complexity: O(n × target)
Space complexity: O(target)

---

Java Code (Bottom-Up DP, Optimal)

class Solution {
    public boolean canPartition(int[] nums) {
        
        int sum = 0;
        for (int n : nums) {
            sum += n;
        }

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

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int s = target; s >= num; s--) {
                if (dp[s - num]) {
                    dp[s] = true;
                }
            }
        }

        return dp[target];
    }
}

Notes:

• Backward traversal ensures each number is used only once (0/1 knapsack).
• dp array keeps track of reachable sums efficiently.

---

Dry Run Example

Input:

nums = [1,5,11,5]

Total sum = 22 → target = 11
Goal: check if any subset sums to 11.

Initialize:

dp = [true, false, false, ..., false] size 12

Process 1

num = 1
Update dp[1] = dp[1-1] = dp[0] = true
dp becomes:

[true, true, false, false, ...]

Process 5

num = 5
Update dp[5] = dp[0] = true
Update dp[6] = dp[1] = true
dp now has reachable sums: 0,1,5,6

Process 11

num = 11
Update dp[11] = dp[0] = true

We found dp[11] = true → subset exists → answer is true.

---

Complexity Analysis

Time:
O(n × target), where target = S/2 and S ≤ 200 × 100 = 20000
Worst-case = about 2 million operations (fast)

Space:
O(target)

---

Edge Cases

• Sum is odd → immediately false
• Single number larger than target → no solution
• All numbers equal → always true if total sum is even
• Very small arrays → trivial checks