Partition Equal Subset Sum in DSA C++

Mental Model

We want to see if we can split a list of numbers into two groups with the same total sum. This means finding a subset that adds up to half the total sum.

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 pick coins for one pile so that its total matches exactly half of all coins combined.

List: [1, 5, 11, 5]
Total sum = 22
Target subset sum = 11
Subset sum problem: Can we pick some numbers to make 11?
[1] [5] [11] [5]
 ↑    ↑    ↑    ↑

Dry Run Walkthrough

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

Goal: Find if we can split the list into two subsets with equal sum (11 each).

Step 1: Calculate total sum and check if it is even

Total sum = 1 + 5 + 11 + 5 = 22 (even)

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

Step 2: Set target subset sum = total sum / 2 = 11

Target = 11

Why: We want to find a subset that sums to 11

Step 3: Use dynamic programming to check if subset sum 11 is possible

Start with empty subset sum 0 possible
Check each number to update possible sums

Why: We build up possible sums step by step

Step 4: Include 1: possible sums now {0,1}

Possible sums: 0 -> 1

Why: Adding 1 allows sum 1

Step 5: Include 5: possible sums now {0,1,5,6}

Possible sums: 0 -> 1 -> 5 -> 6

Why: Adding 5 extends sums by 5

Step 6: Include 11: possible sums now {0,1,5,6,11,12,16,17}

Possible sums: 0 -> 1 -> 5 -> 6 -> 11 -> 12 -> 16 -> 17

Why: Adding 11 extends sums by 11

Step 7: Include last 5: possible sums now include 11 (already found)

Possible sums include 11

Why: Subset sum 11 is possible, so partition exists

Result:

Subset sum 11 found -> Partition possible
Final state: Subset sums include 11

Annotated Code

DSA C++

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

bool canPartition(const vector<int>& nums) {
    int total = 0;
    for (int num : nums) total += num; // sum all numbers
    if (total % 2 != 0) return false; // odd sum means no equal partition
    int target = total / 2;
    vector<bool> dp(target + 1, false);
    dp[0] = true; // zero sum always possible
    for (int num : nums) {
        for (int j = target; j >= num; --j) {
            dp[j] = dp[j] || dp[j - num]; // update sums possible including current num
        }
    }
    return dp[target];
}

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

for (int num : nums) total += num; // sum all numbers

Calculate total sum of all numbers

if (total % 2 != 0) return false; // odd sum means no equal partition

Check if total sum is even; if not, partition impossible

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

Initialize dp array: zero sum is always achievable

for (int num : nums) { for (int j = target; j >= num; --j) { dp[j] = dp[j] || dp[j - num]; } }

Update dp to mark sums achievable by including current number

return dp[target];

Return if target sum is achievable

Output

true

Complexity Analysis

Time: O(n * sum) because we check each number against all sums up to half the total

Space: O(sum) because we use a 1D array of size half the total sum

vs Alternative: Naive approach tries all subsets (2^n), dynamic programming reduces it to polynomial time

Edge Cases

Empty list

Returns true because empty subsets trivially partition equally

DSA C++

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

List with one element

Returns false because cannot split one number into two equal sums

DSA C++

if (total % 2 != 0) return false; // odd sum means no equal partition

List with all zeros

Returns true because zero sum subsets are trivially equal

DSA C++

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

When to Use This Pattern

When asked if a list can be split into two equal sum parts, use the subset sum dynamic programming pattern to check if half the total sum is achievable.

Common Mistakes

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

Mistake: Updating dp array from start to end causing reuse of updated states in the same iteration
Fix: Update dp array backwards from target to num to avoid counting the same number multiple times

Summary

Checks if a list can be split into two subsets with equal sum by finding a subset with sum equal to half the total.

Use when you need to partition a set into two equal sum subsets or check subset sums.

The key insight is that equal partition means finding a subset with sum equal to half the total sum.

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