Partition Equal Subset Sum in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

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

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
    }
    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() {
    nums := []int{1, 5, 11, 5}
    fmt.Println(canPartition(nums))
}

A true

B false

C Compilation error

D Runtime panic

💡 Hint

Think about whether 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. The subsets {11} and {1, 5, 5} both sum to 11. So the function returns true.

🧠 Conceptual

intermediate

Understanding the DP Array in Partition Equal Subset Sum

In the dynamic programming solution for Partition Equal Subset Sum, what does the boolean array dp represent?

A dp[j] stores the count of subsets with sum j

B dp[j] indicates if a subset with sum j can be formed from the elements processed so far

C dp[j] holds the maximum element used to form sum j

D dp[j] indicates if sum j is the total sum of the entire array

💡 Hint

Think about what true or false means for each sum j.

dp[j] is true if there exists a subset of the processed elements that sums exactly to j, otherwise false.

🔧 Debug

advanced

Identify the Bug in Partition Equal Subset Sum Implementation

What error will the following Go code produce when run, and why?

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
    }
    target := total / 2
    dp := make([]bool, target)
    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() {
    nums := []int{1, 5, 11, 5}
    fmt.Println(canPartition(nums))
}

A true

B false

C panic: runtime error: index out of range

D Compilation error

💡 Hint

Check the size of dp and the indices used to access it.

The dp slice is created with length target, but indices go up to target, causing an index out of range panic.

🚀 Application

advanced

Number of Items in DP Array for Partition Equal Subset Sum

Given an input array with total sum S, how many elements does the dp array have in the standard dynamic programming solution for Partition Equal Subset Sum?

A S / 2 + 1

B S + 1

C S / 2

D S

💡 Hint

The dp array size depends on the target sum which is half of total sum.

The dp array size is target + 1 where target = total sum / 2, so size is (S/2) + 1.

❓ Predict Output

expert

Output of Partition Equal Subset Sum with Negative Numbers

What is the output of this Go code that attempts to check partition equal subset sum with negative numbers included?

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
    }
    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() {
    nums := []int{1, -1, 2, 3, 5}
    fmt.Println(canPartition(nums))
}

A false

B true

C Compilation error

D panic: runtime error: index out of range

💡 Hint

Consider how negative numbers affect indexing in dp array.

Negative numbers cause out-of-bounds indices in dp[j-num], leading to runtime panic due to index out of range.

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