Partition Equal Subset Sum in DSA Java

Mental Model

We want to split a list of numbers into two groups with the same total sum. If the total sum is odd, it's impossible. Otherwise, we check if there's a subset that adds up to half the total.

Analogy: Imagine you have a pile of coins and want to divide them into two piles with the same amount of money. You try to find some coins that make exactly half the total value.

Array: [1, 5, 11, 5]
Total sum = 22
Target sum = 11
We want to find a subset that sums to 11.

Dry Run Walkthrough

Input: list: [1, 5, 11, 5]

Goal: Find if we can split the list into two subsets with equal sum

Step 1: Calculate total sum = 1 + 5 + 11 + 5 = 22, check if even

Total sum = 22 (even), target subset sum = 11

Why: If total sum is odd, equal partition is impossible

Step 2: Initialize boolean array dp of size 12 (0 to 11) with dp[0] = true

dp = [true, false, false, false, false, false, false, false, false, false, false, false]

Why: dp[j] means if sum j is possible with some subset

Step 3: Process number 1: update dp for sums from 11 down to 1

dp after 1: [true, true, false, false, false, false, false, false, false, false, false, false]

Why: We can make sum 1 by including number 1

Step 4: Process number 5: update dp for sums from 11 down to 5

dp after 5: [true, true, false, false, false, true, true, false, false, false, false, false]

Why: We can make sums 5 and 6 by including number 5

Step 5: Process number 11: update dp for sums from 11 down to 11

dp after 11: [true, true, false, false, false, true, true, false, false, false, false, true]

Why: We can make sum 11 by including number 11

Step 6: Check dp[11], it is true, so subset with sum 11 exists

dp[11] = true

Why: Found subset that sums to half total, partition possible

Result:

dp array shows dp[11] = true, so partition is possible

Annotated Code

DSA Java

public class PartitionEqualSubsetSum {
    public static boolean canPartition(int[] nums) {
        int totalSum = 0;
        for (int num : nums) {
            totalSum += num;
        }
        if (totalSum % 2 != 0) return false; // odd sum can't be split equally
        int target = totalSum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // zero sum is always possible
        for (int num : nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num]; // update dp if sum j can be formed
            }
        }
        return dp[target];
    }

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

if (totalSum % 2 != 0) return false; // odd sum can't be split equally

Check if total sum is odd, return false early

dp[0] = true; // zero sum is always possible

Initialize dp for zero sum

for (int num : nums) {

Iterate over each number to update dp

for (int j = target; j >= num; j--) {

Traverse dp backwards to avoid reuse of same number in this iteration

dp[j] = dp[j] || dp[j - num]; // update dp if sum j can be formed

Update dp to reflect if sum j is possible including current number

return dp[target];

Return if target sum subset exists

Output

true

Complexity Analysis

Time: O(n * sum) because we iterate over all numbers and for each number update dp array up to target sum

Space: O(sum) because dp array stores boolean values for sums up to target

vs Alternative: Naive approach tries all subsets with exponential time; this dynamic programming approach is efficient and polynomial

Edge Cases

empty array

returns true because zero sum can be partitioned trivially

DSA Java

dp[0] = true; // zero sum is always possible

array with one element

returns false if element is not zero because can't split one number into two equal subsets

DSA Java

if (totalSum % 2 != 0) return false; // odd sum can't be split equally

array with all zeros

returns true because sum is zero and can be partitioned

DSA Java

dp[0] = true; // zero sum is always possible

When to Use This Pattern

When you see a problem asking if a list can be split into two equal sum parts, reach for the Partition Equal Subset Sum pattern using subset sum dynamic programming.

Common Mistakes

Mistake: Iterating dp array forwards causing reuse of the same number multiple times in one iteration
Fix: Iterate dp array backwards from target to num to avoid counting the same number multiple times

Mistake: Not checking if total sum is even before proceeding
Fix: Add early check to return false if total sum is odd

Summary

Checks if array can be split into two subsets with equal sum using dynamic programming.

Use when you need to find if a subset with half the total sum exists.

The key insight is to reduce the problem to finding a subset with sum equal to half the total.

Practice

1. What does the Partition Equal Subset Sum problem ask you to determine about a given array of positive integers?

easy

A. If the array can be split into two subsets with equal sums

B. If the array contains any duplicate elements

C. If the array is sorted in ascending order

D. If the array contains only even numbers

Solution

1. Step 1: Understand the problem statement

   The problem asks whether the array can be divided into two parts where the sum of elements in both parts is the same.

2. Step 2: Identify the key condition

   This means the total sum of the array must be even and there must be a subset with sum equal to half of the total sum.

3. Final Answer:

   If the array can be split into two subsets with equal sums -> Option A

4. Quick Check:

   Partition Equal Subset Sum = Split array into two equal sum subsets [OK]

Hint: Check if total sum is even first to decide quickly [OK]

Common Mistakes:

• Thinking the problem is about sorting the array
• Confusing equal sum subsets with duplicate elements
• Ignoring the sum condition and just checking elements

2. Which of the following Java method signatures correctly represents a function to solve the Partition Equal Subset Sum problem?

easy

A. public boolean canPartition(int[] nums)

B. public int canPartition(int[] nums)

C. public void canPartition(int[] nums)

D. public String canPartition(int nums)

Solution

1. Step 1: Identify the return type

   The function should return true or false, so the return type must be boolean.

2. Step 2: Check parameter type

   The input is an array of integers, so parameter should be int[] nums.

3. Final Answer:

   public boolean canPartition(int[] nums) -> Option A

4. Quick Check:

   Boolean return + int array parameter = public boolean canPartition(int[] nums) [OK]

Hint: Return boolean for yes/no problems [OK]

Common Mistakes:

• Using int return type instead of boolean
• Using void return type which gives no answer
• Passing single int instead of int array

3. What will be the output of the following Java code snippet?

int[] nums = {1, 5, 11, 5};
System.out.println(canPartition(nums));

public static boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    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 i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

medium

A. Compilation error

B. false

C. true

D. Runtime exception

Solution

1. Step 1: Calculate total sum and check parity

   Sum = 1+5+11+5 = 22, which is even, so continue.

2. Step 2: Use dynamic programming to check subset sum

   The dp array tracks sums achievable. The subset {11, 5, 5} sums to 21, but target is 11. Actually, subset {11} and {1,5,5} both sum to 11, so dp[target] becomes true.

3. Final Answer:

   true -> Option C

4. Quick Check:

   Subset sum equals half total sum = true [OK]

Hint: Check if half sum subset exists using dp array [OK]

Common Mistakes:

• Not checking if total sum is even first
• Confusing dp array update direction
• Assuming subset must be contiguous

4. Identify the bug in this Java method for Partition Equal Subset Sum:

public boolean canPartition(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    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 i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

medium

A. The dp array size is incorrect

B. The sum parity check condition is reversed

C. The inner loop should increment i instead of decrement

D. The method should return int instead of boolean

Solution

1. Step 1: Check sum parity condition

   The code returns false if sum % 2 == 0, but it should return false if sum is odd (sum % 2 != 0).

2. Step 2: Verify other parts

   dp array size and loops are correct; only the parity check is wrong.

3. Final Answer:

   The sum parity check condition is reversed -> Option B

4. Quick Check:

   Return false if sum is odd, not even [OK]

Hint: Remember: odd sum means no equal partition [OK]

Common Mistakes:

• Returning false when sum is even instead of odd
• Changing dp array size incorrectly
• Looping forward instead of backward causing wrong dp updates

5. Given the array nums = {2, 2, 3, 5}, which of the following modifications to the standard Partition Equal Subset Sum approach will correctly determine if the array can be partitioned into two subsets with equal sum, considering that elements can be used multiple times?

hard

A. Use a recursive approach without memoization

B. Keep the inner loop backward but initialize dp[1] = true

C. Double the target sum before processing

D. Change the inner loop to iterate from num to target (forward) instead of backward

Solution

1. Step 1: Understand the problem change

   Allowing elements multiple times means this is an unbounded subset sum problem, requiring forward iteration in dp update.

2. Step 2: Modify dp iteration accordingly

   Changing the inner loop to go from num to target (forward) allows reusing elements multiple times correctly.

3. Step 3: Verify other options

   Initializing dp[1] is incorrect; recursion without memo is inefficient; doubling target sum is wrong.

4. Final Answer:

   Change the inner loop to iterate from num to target (forward) instead of backward -> Option D

5. Quick Check:

   Unbounded subset sum needs forward dp loop [OK]

Hint: For repeated elements, loop forward in dp array [OK]

Common Mistakes:

• Using backward loop for repeated elements
• Incorrect dp initialization
• Ignoring efficiency by using recursion without memo