Partition Equal Subset Sum in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

What is the output of the following Java code that checks if the array can be partitioned into two subsets with equal sum?

DSA Java

public class Solution {
    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 j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

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

A false

B true

C Compilation error

D Runtime exception

💡 Hint

Check if the total sum is even and then use dynamic programming to find subset with half sum.

The total sum is 22 which is even. The code uses a boolean DP array to check if a subset sums to 11. Since {1,5,5} sums to 11, the output is true.

❓ Predict Output

intermediate

Output for No Equal Partition Possible

What will be the output of this Java code for the input array where partition into equal sum subsets is not possible?

DSA Java

public class Solution {
    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 j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

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

A false

B true

C Compilation error

D Runtime exception

💡 Hint

Sum is 11 which is odd, so partition is impossible.

The sum of the array is 11 which is odd, so it cannot be split into two equal subsets. The function returns false.

🧠 Conceptual

advanced

Understanding the DP Array in Partition Equal Subset Sum

In the Partition Equal Subset Sum problem, what does the boolean DP array represent during the computation?

A dp[i] indicates if a subset with sum i can be formed from the elements processed so far

B dp[i] stores the count of subsets that sum to i

C dp[i] indicates if the sum i is the total sum of the array

D dp[i] stores the maximum element used to form sum i

💡 Hint

Think about what true or false means for each sum index in dp.

Each dp[i] is true if there exists a subset of the input numbers that sums exactly to i. This helps to check if half the total sum can be formed.

🔧 Debug

advanced

Identify the Bug in Partition Equal Subset Sum Implementation

What is the bug in the following Java code snippet for Partition Equal Subset Sum?

DSA Java

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];
    dp[0] = true;
    for (int num : nums) {
        for (int j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

A The sum check should be sum % 3 != 0 instead of sum % 2 != 0

B The loop should run from j = num to target, not backwards

C dp[0] should be initialized to false

D dp array size should be target + 1, not target

💡 Hint

Check array size and indexing carefully.

The dp array must have size target + 1 to include index target. Using size target causes ArrayIndexOutOfBoundsException when accessing dp[target].

🚀 Application

expert

Number of Subsets with Sum Equal to Half Total

Given an array of positive integers, how can you modify the Partition Equal Subset Sum approach to find the number of subsets that sum to half the total sum?

A Use a boolean DP array and count true values after processing all elements

B Use recursion without memoization to count subsets

C Use an integer DP array where dp[i] stores the count of subsets summing to i, updating dp[j] += dp[j - num]

D Use a stack to store subsets and count them after processing

💡 Hint

Counting subsets requires summing counts, not just true/false.

To count subsets, use an integer dp array where dp[i] holds the number of subsets summing to i. For each num, update dp[j] += dp[j - num] for j from target down to num.

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