Partition Equal Subset Sum in DSA Go

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 equal piles. You try picking some coins to make one pile exactly half the total value.

Array: [1, 5, 11, 5]
Total sum = 22
Target subset sum = 11
Subset search: [] -> trying to find subset with sum 11

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 even

Total sum = 22, target subset sum = 11

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

Step 2: Start checking subsets to find sum 11 using dynamic programming

DP array initialized: dp[0] = true (sum 0 is always possible)

Why: We build up possible sums from smaller subsets

Step 3: Include number 1: update dp for sums including 1

dp[1] = true (sum 1 possible), dp[0] = true

Why: Adding 1 allows sum 1 to be possible

Step 4: Include number 5: update dp for sums including 5

dp[5] = true, dp[6] = true (1+5), dp[1] = true, dp[0] = true

Why: Adding 5 allows sums 5 and 6

Step 5: Include number 11: update dp for sums including 11

dp[11] = true (directly from 11), dp[6], dp[5], dp[1], dp[0] remain true

Why: Adding 11 directly achieves target sum

Step 6: Check dp[target] which is dp[11]

dp[11] = true

Why: True means subset with sum 11 exists, so partition possible

Result:

dp array shows dp[11] = true
Answer: Partition possible
Subset example: [11] and [1,5,5]

Annotated Code

DSA Go

package main

import "fmt"

func canPartition(nums []int) bool {
	total := 0
	for _, num := range nums {
		total += num
	}
	if total%2 != 0 {
		return false // odd total sum means no equal partition
	}
	target := total / 2
	dp := make([]bool, target+1)
	dp[0] = true // sum 0 is always possible

	for _, num := range nums {
		for j := target; j >= num; j-- {
			if dp[j-num] {
				dp[j] = true // update dp for current sum
			}
		}
	}

	return dp[target]
}

func main() {
	nums := []int{1, 5, 11, 5}
	if canPartition(nums) {
		fmt.Println("Partition possible")
	} else {
		fmt.Println("Partition not possible")
	}
}

if total%2 != 0 { return false }

Check if total sum is odd; if yes, partition impossible

dp[0] = true

Initialize dp to mark sum 0 as achievable

for _, num := range nums { for j := target; j >= num; j-- { if dp[j-num] { dp[j] = true } } }

Update dp array to mark sums achievable by including current number

return dp[target]

Return if target sum is achievable

Output

Partition possible

Complexity Analysis

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

Space: O(sum) because we use a dp array of size target+1

vs Alternative: Naive approach tries all subsets with exponential time; DP reduces it to polynomial time

Edge Cases

Empty list

Returns true because two empty subsets have equal sum zero

DSA Go

dp[0] = true

List with one element

Returns false because cannot split one number into two equal subsets

DSA Go

if total%2 != 0 { return false }

List with all zeros

Returns true because sum is zero and subsets can be equal

DSA Go

dp[0] = true

When to Use This Pattern

When asked if a list can be split into two equal sum parts, use subset sum dynamic programming to find 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 same iteration
Fix: Update dp array backwards from target to current number to avoid reuse

Summary

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

Use when you need to partition a set into two equal sum subsets.

The key is to find a subset with sum equal to half the total sum.

Practice

1. What does the Partition Equal Subset Sum problem ask you to find?

easy

A. If the array contains any duplicate elements

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

C. If the array is sorted in ascending order

D. If the array contains only positive numbers

Solution

1. Step 1: Understand the problem goal

   The problem asks if we can divide the array into two parts where the sum of numbers in both parts is the same.

2. Step 2: Clarify what is being checked

   We are not checking duplicates, sorting, or positivity, only if such a partition exists.

3. Final Answer:

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

4. Quick Check:

   Partition Equal Subset Sum = split array equally [OK]

Hint: Look for equal sum split, not sorting or duplicates [OK]

Common Mistakes:

• Confusing partition with sorting
• Checking for duplicates instead of sums
• Assuming all numbers must be positive

2. Which of the following Go function signatures is correct for a function that checks Partition Equal Subset Sum on an integer slice?

easy

A. func canPartition(nums []int) bool

B. func canPartition(nums int) bool

C. func canPartition(nums []int) int

D. func canPartition(nums []string) bool

Solution

1. Step 1: Identify correct parameter type

   The function should accept a slice of integers, so []int is correct.

2. Step 2: Identify correct return type

   The function returns true or false, so return type must be bool.

3. Final Answer:

   func canPartition(nums []int) bool -> Option A

4. Quick Check:

   Function takes []int and returns bool [OK]

Hint: Input slice of int, output bool for yes/no [OK]

Common Mistakes:

• Using int instead of []int as parameter
• Returning int instead of bool
• Using wrong slice type like []string

3. What is the output of the following Go code?

package main
import "fmt"
func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total%2 != 0 {
        return false
    }
    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, num := range nums {
        for j := target; j >= num; j-- {
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}
func main() {
    fmt.Println(canPartition([]int{1, 5, 11, 5}))
    fmt.Println(canPartition([]int{1, 2, 3, 5}))
}

medium

A. true
true

B. false
true

C. true
false

D. false
false

Solution

1. Step 1: Calculate total sums and check parity

   For [1,5,11,5], sum=22 (even), for [1,2,3,5], sum=11 (odd). Odd sum means no equal partition.

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

   For first array, dp[target] becomes true, so returns true. For second, returns false.

3. Final Answer:

   true false -> Option C

4. Quick Check:

   Even sum array returns true, odd sum returns false [OK]

Hint: Check if total sum is even, then use subset sum DP [OK]

Common Mistakes:

• Ignoring sum parity check
• Incorrect DP update order
• Returning wrong boolean values

4. Identify the bug in this Go function for Partition Equal Subset Sum:

func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total%2 == 1 {
        return false
    }
    target := total / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, num := range nums {
        for j := num; j <= target; j++ {
            dp[j] = dp[j] || dp[j-num]
        }
    }
    return dp[target]
}

medium

A. The inner loop should run backwards from target to num

B. The total sum check should be total%2 != 0

C. dp slice should be of size target, not target+1

D. dp[0] should be initialized to false

Solution

1. Step 1: Analyze the inner loop direction

   The inner loop runs from num to target increasing, which causes dp to use updated values in the same iteration, leading to incorrect results.

2. Step 2: Correct loop direction for subset sum DP

   The loop should run backwards from target down to num to avoid using updated dp values prematurely.

3. Final Answer:

   The inner loop should run backwards from target to num -> Option A

4. Quick Check:

   Loop backwards to avoid dp overwrite [OK]

Hint: Loop backwards in DP to prevent using updated states [OK]

Common Mistakes:

• Looping forwards in DP causing wrong results
• Incorrect parity check condition
• Wrong dp slice size
• Wrong dp[0] initialization

5. Given the array [2, 2, 3, 5], which of the following modifications to the Partition Equal Subset Sum algorithm will correctly identify if the array can be partitioned into two subsets with equal sum, considering that the array may contain zero or negative numbers?

hard

A. Use a greedy approach by picking the largest numbers first

B. Ignore negative numbers and proceed with the standard DP approach

C. Sort the array first and then apply the standard DP algorithm

D. Adjust the algorithm to handle negative numbers by offsetting sums and using a 2D DP array

Solution

1. Step 1: Understand the limitation of standard DP

   The standard DP approach assumes all numbers are positive, so negative numbers break the indexing logic.

2. Step 2: Modify algorithm for negative numbers

   Offset sums to make all numbers non-negative and use a 2D DP array to track possible sums including negatives.

3. Step 3: Check if partition is possible with adjusted DP

   This approach correctly handles zero and negative values, unlike ignoring or sorting.

4. Final Answer:

   Adjust the algorithm to handle negative numbers by offsetting sums and using a 2D DP array -> Option D

5. Quick Check:

   Handle negatives with offset and 2D DP [OK]

Hint: Use offset and 2D DP for negatives, not greedy or sorting [OK]

Common Mistakes:

• Ignoring negative numbers causes wrong results
• Sorting does not fix negative sum indexing
• Greedy approach fails for equal partition