Partition Equal Subset Sum in DSA Go - Execution Trace

Concept Flow - Partition Equal Subset Sum

Calculate total sum of array

↓

Check if sum is odd?

Yes→Return False: cannot partition

No↓

Set target = sum/2

↓

Use DP to check if subset sums to target

↓

If subset found

Yes→Return True

No↓

Return False

We first find the total sum. If it's odd, partition is impossible. Otherwise, we try to find a subset with sum equal to half the total using dynamic programming.

Execution Sample

DSA Go

nums := []int{1, 5, 11, 5}
result := canPartition(nums)
fmt.Println(result)

Check if array [1,5,11,5] can be split into two subsets with equal sum.

Execution Table

Step	Operation	Subset Sum Target	DP Table State	Result
1	Calculate total sum	-	sum=22	-
2	Check if sum is odd	22	-	No, continue
3	Set target = sum/2	11	-	-
4	Initialize DP table	11	[true, false, false, false, false, false, false, false, false, false, false, false]	-
5	Process num=1	11	[true, true, false, false, false, false, false, false, false, false, false, false]	-
6	Process num=5	11	[true, true, false, false, false, true, true, false, false, false, false, false]	-
7	Process num=11	11	[true, true, false, false, false, true, true, false, false, false, false, true]	-
8	Process num=5	11	[true, true, false, false, false, true, true, false, false, false, true, true]	-
9	Check dp[target]	11	-	True (subset found)
10	Return result	-	-	True

💡 DP table shows subset with sum 11 exists, so partition is possible.

Variable Tracker

Variable	Start	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
sum	0	22	22	22	22	22	22
target	0	11	11	11	11	11	11
dp	nil	[true, false, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, false, false, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, false]	[true, true, false, false, false, true, true, false, false, false, false, true]	[true, true, false, false, false, true, true, false, false, false, true, true]	[true, true, false, false, false, true, true, false, false, false, true, true]

Key Moments - 3 Insights

Why do we return false immediately if the total sum is odd?

Because two equal subsets must each sum to half the total. If total sum is odd, half is not an integer, so partition is impossible. See execution_table step 2.

How does the DP table represent possible subset sums?

dp[i] is true if a subset sums to i. Initially dp[0] is true (empty subset). We update dp by including each number. See execution_table steps 4-8.

Why do we check dp[target] at the end?

Because target is half the total sum. If dp[target] is true, a subset sums to target, so partition is possible. See execution_table step 9.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what does dp[1] become after processing num=1?

A undefined

B true

C false

D remains true

💡 Hint

Check dp table state in step 5 row, dp[1] changes from false to true after including 1.

At which step does the DP table first show that sum 11 is achievable?

A Step 7

B Step 6

C Step 8

D Step 9

💡 Hint

Look at DP table state in step 7, dp[11] becomes true for the first time.

If the input array was [1, 2, 3, 5], how would the final dp[target] change?

A It would be true

B It would be undefined

C It would be false

D It would depend on order

💡 Hint

Sum is 11, target 5.5 (odd sum), so partition impossible. See key_moments about odd sums.

Concept Snapshot

Partition Equal Subset Sum:
- Find total sum of array
- If sum is odd, return false
- Else, target = sum/2
- Use DP boolean array dp of size target+1
- dp[0] = true (empty subset)
- For each num, update dp[i] |= dp[i-num]
- Return dp[target]

Full Transcript

The Partition Equal Subset Sum problem checks if an array can be split into two subsets with equal sums. We first calculate the total sum. If the sum is odd, partition is impossible and we return false immediately. Otherwise, we set the target as half the total sum. We use a dynamic programming approach with a boolean array dp where dp[i] indicates if a subset sums to i. We initialize dp[0] as true because an empty subset sums to zero. For each number in the array, we update dp from the target down to the number, setting dp[i] to true if dp[i - num] was true. After processing all numbers, if dp[target] is true, it means a subset with sum equal to half the total exists, so partition is possible and we return true. Otherwise, we return false. The execution table traces these steps with the dp table states after processing each number, showing how the subset sums build up to the target.

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