Partition Equal Subset Sum

Master this topic with zero to advance depth.

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.

Visual Representation

nums = [1, 5, 11, 5]
Total Sum = 22, Target = 11

Subsets:
[1, 5, 5] -> Sum 11
[11] -> Sum 11
Result: True

Logic:
Can we find a subset with sum equal to (TotalSum / 2)?

Medium

Examples

Input: nums = [1, 5, 11, 5]
Output: true
The array can be partitioned as [1, 5, 5] and [11].

Input: nums = [1, 2, 3, 5]
Output: false

Approach 1

Level I: Dynamic Programming (Bottom-Up 2D)

Intuition

This is a variation of the 0/1 Knapsack Problem. We want to find if there's a subset with sum = totalSum / 2.

Thought Process

If totalSum is odd, return false (cannot partition equally).
Target = totalSum / 2.
dp[i][j] = true if sum j can be formed using first i elements.
dp[i][j] = dp[i-1][j] (exclude current) OR dp[i-1][j - nums[i]] (include current, if j >= nums[i]).

⏱ O(N * Target)💾 O(N * Target)

Detailed Dry Run

nums = [1, 5, 5], Target = 5.5 (Skip, 11 is total) nums = [1, 2, 3], Target = 3

i	x	Sum 0	Sum 1	Sum 2	Sum 3	Action
0	1	T	T	F	F	Init
1	2	T	T	T	T	dp[0][3]
Result					T	True!

java

public class Main {
    public static 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[nums.length + 1][target + 1];
        for (int i = 0; i <= nums.length; i++) dp[i][0] = true;

        for (int i = 1; i <= nums.length; i++) {
            for (int j = 1; j <= target; j++) {
                dp[i][j] = dp[i-1][j];
                if (j >= nums[i-1]) {
                    dp[i][j] = dp[i][j] || dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[nums.length][target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5})); // true
    }
}

Approach 2

Level II: Memoization (Top-Down)

Intuition

The 2D DP bottom-up approach explores the entire grid. A top-down memoized approach explores only the reachable states. Both have the same complexity but memoization is more intuitive to derive.

Visual

nums=[1,5,11,5], target=11
solve(4, 11): can_pick(11)? No, but 11<11 is false for nums[3]=5
solve(3, 6): can_pick(11)? ...

⏱ O(N * Target)💾 O(N * Target)

Detailed Dry Run

nums=[1,5,5,11], target=11. solve(3, 11) = take 11 = solve(2, 0) = True! Cached.

java

import java.util.*;

public class Main {
    static Map<String, Boolean> memo = new HashMap<>();
    public static boolean solve(int[] nums, int i, int target) {
        if (target == 0) return true;
        if (i == 0 || target < 0) return false;
        String key = i + "_" + target;
        if (memo.containsKey(key)) return memo.get(key);
        boolean result = solve(nums, i - 1, target - nums[i - 1]) || solve(nums, i - 1, target);
        memo.put(key, result);
        return result;
    }

    public static boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        if (sum % 2 != 0) return false;
        return solve(nums, nums.length, sum / 2);
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 5, 11, 5})); // true
    }
}

⚠️ Common Pitfalls & Tips

String keys for memoization in C++/Go/Java are slow. A 2D boolean array with i and t as indices is faster and preferred in practice.

Approach 3

Level III: Space Optimized (1D)

Intuition

Since dp[i][j] only depends on the previous row dp[i-1], we can use a single row array. To avoid using the same element twice for the same sum (0/1 constraint), we iterate the sum backwards.

Logic Steps

Initialize a dp array of size target + 1 with false.
dp[0] = true.
For each num in nums:
- For j from target down to num:
  - dp[j] = dp[j] || dp[j - num].

⏱ O(N * Target)💾 O(Target)

Detailed Dry Run

nums = [1, 2, 3], Target = 3

num	Target 3	Target 2	Target 1	Target 0
-	F	F	F	T
1	F	F	T (0+1)	T
2	T (1+2)	T (0+2)	T	T
3	T (0+3)	T	T	T

java

public class Main {
    public static 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 n : nums) {
            for (int j = target; j >= n; j--) {
                dp[j] = dp[j] || dp[j - n];
            }
        }
        return dp[target];
    }

    public static void main(String[] args) {
        System.out.println(canPartition(new int[]{1, 2, 3, 5})); // false
    }
}

⚠️ Common Pitfalls & Tips

You must iterate the inner loop backwards (from target to num). If you iterate forwards, you might use the same element multiple times for the same sum (which is unbounded knapsack behavior, not 0/1).

← Previous QuestionWord Break

Next Question →Climbing Stairs

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.