Partition Equal Subset Sum in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subset sum check for equal partition

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

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

int main() {
    vector<int> nums = {1, 5, 11, 5};
    cout << (canPartition(nums) ? "true" : "false") << endl;
    return 0;
}

A true

B false

C Compilation error

D Runtime error

💡 Hint

Check if the total sum is even and if a subset sums to half the total.

The total sum is 22, which is even. Half is 11. Subsets {1,5,5} and {11} both sum to 11, so partition is possible. Output is true.

🧠 Conceptual

intermediate

Understanding the base case in Partition Equal Subset Sum

In the dynamic programming solution for Partition Equal Subset Sum, why do we initialize dp[0] = true?

A Because a subset with sum zero is always possible (empty subset).

B Because zero is the smallest number in the array.

C Because it marks the end of the array traversal.

D Because it indicates the total sum is zero.

💡 Hint

Think about what sum zero means for subsets.

dp[0] = true means that we can always form a subset with sum zero by choosing no elements (empty subset). This is the base case for building up solutions.

🔧 Debug

advanced

Identify the error in this Partition Equal Subset Sum code snippet

What error will this code produce when run?

DSA C++

#include <vector>
using namespace std;

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<bool> dp(target, false);
    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 Returns incorrect result for some inputs

B Compilation error: cannot assign to dp[0]

C Runtime error: out_of_range exception

D No error, works correctly

💡 Hint

Check the size of dp vector and the indices accessed.

The dp vector is initialized with size 'target', but indices go up to 'target'. Accessing dp[target] causes out_of_range error.

🚀 Application

advanced

Number of subsets with sum equal to half total

Given the array {2, 2, 3, 5}, how many subsets sum to half of the total sum?

A 1

B 0

C 3

D 2

💡 Hint

Calculate total sum, then find subsets summing to half.

Total sum is 12, half is 6. No subset sums to 6 (e.g., 2+2+3=7, 2+3=5, 2+2=4, etc.). Thus, 0 subsets.

❓ Predict Output

expert

Output of recursive Partition Equal Subset Sum with memoization

What is the output of this C++ code that uses recursion and memoization to check partition?

DSA C++

#include <iostream>
#include <vector>
using namespace std;

bool dfs(int idx, int target, vector<int>& nums, vector<vector<int>>& memo) {
    if (target == 0) return true;
    if (idx >= nums.size() || target < 0) return false;
    if (memo[idx][target] != -1) return memo[idx][target];
    bool include = dfs(idx + 1, target - nums[idx], nums, memo);
    bool exclude = dfs(idx + 1, target, nums, memo);
    memo[idx][target] = include || exclude;
    return memo[idx][target];
}

bool canPartition(vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    vector<vector<int>> memo(nums.size(), vector<int>(target + 1, -1));
    return dfs(0, target, nums, memo);
}

int main() {
    vector<int> nums = {1, 2, 3, 5};
    cout << (canPartition(nums) ? "true" : "false") << endl;
    return 0;
}

A true

B Runtime error

C Compilation error

D false

💡 Hint

Check if the sum is even and if a subset sums to half.

Sum is 11, which is odd, so partition is impossible. The code returns false.

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 into equal sum subsets [OK]

Hint: Check if total sum is even to start [OK]

Common Mistakes:

• Thinking it checks for duplicates
• Assuming sorting is required
• Confusing with subset sum existence

2. Which of the following C++ code snippets correctly initializes a boolean DP array for the Partition Equal Subset Sum problem with size (sum/2 + 1) and sets the base case?

easy

A. bool dp[sum / 2 + 1]; std::fill(dp, dp + sum / 2 + 1, false); dp[0] = true;

B. std::vector<int> dp(sum / 2 + 1, 0); dp[0] = 1;

C. std::vector<bool> dp(sum / 2 + 1, false); dp[0] = true;

D. std::vector<bool> dp(sum + 1, false); dp[sum] = true;

Solution

1. Step 1: Choose correct data type and size

   We need a boolean vector of size (sum/2 + 1) to track subset sums. std::vector<bool> dp(sum / 2 + 1, false); dp[0] = true; uses correct size and type.

2. Step 2: Set base case correctly

   dp[0] = true means sum zero is always possible. std::vector<bool> dp(sum / 2 + 1, false); dp[0] = true; does this correctly. std::vector<int> dp(sum / 2 + 1, 0); dp[0] = 1; uses int vector, which is less appropriate. std::vector<bool> dp(sum + 1, false); dp[sum] = true; uses wrong size and sets dp[sum] instead of dp[0].

3. Final Answer:

   std::vector<bool> dp(sum / 2 + 1, false); dp[0] = true; -> Option C

4. Quick Check:

   Boolean vector with dp[0] true = Correct initialization [OK]

Hint: Use bool vector and set dp[0] = true for base case [OK]

Common Mistakes:

• Using int vector instead of bool
• Incorrect dp array size
• Setting wrong base case index

3. What is the output of the following C++ code snippet for the input array {1, 5, 11, 5}?

bool canPartition(std::vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    std::vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

int main() {
    std::vector<int> nums = {1, 5, 11, 5};
    std::cout << (canPartition(nums) ? "true" : "false") << std::endl;
    return 0;
}

medium

A. true

B. false

C. Compilation error

D. Runtime error

Solution

1. Step 1: Calculate total sum and check parity

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

2. Step 2: Use DP to check subset sum of 11

   The code uses a boolean dp array to check if subset sum 11 is possible. The subsets {11} and {1,5,5} both sum to 11, so dp[11] becomes true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Subset sum 11 exists = true [OK]

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

Common Mistakes:

• Assuming sum odd means true
• Not iterating dp backwards
• Confusing output with subset elements

4. Identify the bug in the following code snippet for Partition Equal Subset Sum and select the fix:

bool canPartition(std::vector<int>& nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    std::vector<bool> dp(target + 1, false);
    dp[0] = true;
    for (int num : nums) {
        for (int j = num; j <= target; ++j) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

medium

A. Change sum check to if (sum % 2 == 0) return false

B. Initialize dp vector with true instead of false

C. Remove dp[0] = true assignment

D. Change inner loop to iterate backwards: for (int j = target; j >= num; --j)

Solution

1. Step 1: Analyze inner loop direction

   The inner loop iterates forwards, which causes dp to use updated values in the same iteration, leading to incorrect results.

2. Step 2: Correct loop direction

   Iterating backwards ensures dp[j - num] uses values from previous iteration, preserving correctness.

3. Final Answer:

   Change inner loop to iterate backwards: for (int j = target; j >= num; --j) -> Option D

4. Quick Check:

   Backward iteration in DP loop fixes state update [OK]

Hint: Iterate dp array backwards to avoid overwriting states [OK]

Common Mistakes:

• Iterating dp forwards causing wrong results
• Incorrect dp initialization
• Wrong sum parity check

5. Given the array {2, 2, 3, 5}, which of the following statements is true regarding the Partition Equal Subset Sum problem?

hard

A. The array can be partitioned into two subsets with equal sum: {2,3} and {2,5}

B. The array cannot be partitioned into two subsets with equal sum because no subset sums to half the total

C. The array can be partitioned into two subsets with equal sum: {2,2,3} and {5}

D. The array cannot be partitioned into two subsets with equal sum because total sum is odd

Solution

1. Step 1: Calculate total sum

   Sum = 2 + 2 + 3 + 5 = 12, which is even, so partition might be possible.

2. Step 2: Check for subset with sum 6

   Half sum = 6. Possible subsets: - {2,2,3} sum = 7 (too high) - {2,3} sum = 5 (too low) - {5} sum = 5 (too low) - {2,2} sum = 4 (too low) No subset sums exactly to 6.

3. Final Answer:

   The array cannot be partitioned into two subsets with equal sum because no subset sums to half the total -> Option B

4. Quick Check:

   Half sum subset missing = No partition [OK]

Hint: Check if half sum subset exists before concluding [OK]

Common Mistakes:

• Assuming total sum even means partition possible
• Incorrect subset sums calculation
• Confusing subsets with unequal sums