Partition Equal Subset Sum in DSA Go - Build from Scratch

Partition Equal Subset Sum

📖 Scenario: You have a list of item weights that you want to pack into two boxes. You want to check if it's possible to split the items so both boxes have the same total weight.

🎯 Goal: Build a program that checks if the list of weights can be divided into two groups with equal sum.

📋 What You'll Learn

Create a slice called weights with the exact values: 1, 5, 11, 5

Create an integer variable called totalSum to hold the sum of all weights

Write a function called canPartition that takes weights and returns true if the weights can be split into two equal sum subsets, otherwise false

Print the result of canPartition(weights) as true or false

💡 Why This Matters

🌍 Real World

Packing items evenly into two boxes or dividing tasks evenly between two workers.

💼 Career

Understanding subset sum problems helps in optimization, resource allocation, and algorithm design roles.

1

Create the weights slice

Create a slice called weights with the exact values: 1, 5, 11, 5

DSA Go

# Create the weights slice with values 1, 5, 11, 5
# Your code here

Hint

Use weights := []int{1, 5, 11, 5} to create the slice.

2

Calculate the total sum of weights

Create an integer variable called totalSum and set it to the sum of all elements in weights using a for loop

DSA Go

package main

func main() {
    weights := []int{1, 5, 11, 5}
    // Calculate totalSum of weights
    // Your code here
}

Hint

Use totalSum := 0 and a for _, weight := range weights loop to add each weight to totalSum.

3

Write the canPartition function

Write a function called canPartition that takes a slice of integers called weights and returns a boolean. The function should return false if the total sum of weights is odd. Otherwise, use a boolean slice called dp to check if a subset with sum equal to half of total sum exists. Return dp[target] where target is half of total sum.

DSA Go

package main

func canPartition(weights []int) bool {
    // Your code here
}

func main() {
    weights := []int{1, 5, 11, 5}
    totalSum := 0
    for _, weight := range weights {
        totalSum += weight
    }
}

Hint

Use dynamic programming with a boolean slice dp to track reachable sums up to target.

4

Print the result of canPartition

Print the result of calling canPartition(weights) using fmt.Println

DSA Go

package main

import "fmt"

func canPartition(weights []int) bool {
    totalSum := 0
    for _, weight := range weights {
        totalSum += weight
    }
    if totalSum%2 != 0 {
        return false
    }
    target := totalSum / 2
    dp := make([]bool, target+1)
    dp[0] = true
    for _, weight := range weights {
        for j := target; j >= weight; j-- {
            dp[j] = dp[j] || dp[j-weight]
        }
    }
    return dp[target]
}

func main() {
    weights := []int{1, 5, 11, 5}
    totalSum := 0
    for _, weight := range weights {
        totalSum += weight
    }
    // Print the result of canPartition(weights)
    // Your code here
}

Hint

Use fmt.Println(canPartition(weights)) to print the result.

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