Partition Equal Subset Sum in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to calculate the total sum of the array.

DSA Go

func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += [1]
    }
    return false
}

Drag options to blanks, or click blank then click option'

A0

Bnums

Ctotal

Dnum

Attempts:

3 left

💡 Hint

Common Mistakes

Using the whole array 'nums' instead of the current element.

Adding zero instead of the current number.

We add each element 'num' from the array 'nums' to the total sum.

2fill in blank

medium

Complete the code to check if the total sum is odd, return false immediately.

DSA Go

func canPartition(nums []int) bool {
    total := 0
    for _, num := range nums {
        total += num
    }
    if total [1] 2 != 0 {
        return false
    }
    return true
}

Drag options to blanks, or click blank then click option'

A==

B/

C%

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using division '/' instead of modulus '%'.

Using equality '==' instead of modulus.

We use the modulus operator '%' to check if total is odd by checking remainder when divided by 2.

3fill in blank

hard

Fix the error in the code to initialize the dp slice with correct size.

DSA Go

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, [1])
    dp[0] = true
    return false
}

Drag options to blanks, or click blank then click option'

Atarget + 1

Btotal

Clen(nums)

Dtarget

Attempts:

3 left

💡 Hint

Common Mistakes

Using total instead of target for dp size.

Using target without adding 1, causing index errors.

We create a boolean slice dp of size target+1 to represent sums from 0 to target.

4fill in blank

hard

Fill both blanks to update dp slice correctly for each number.

DSA Go

for _, num := range nums {
    for j := [1]; j >= num; j-- {
        dp[j] = dp[j] || dp[j [2] num]
    }
}

Drag options to blanks, or click blank then click option'

Atarget

B+

C-

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Looping forward instead of backward causing incorrect dp updates.

Using addition instead of subtraction inside dp index.

We iterate backward from target down to num, and update dp[j] by checking dp[j] or dp[j - num].

5fill in blank

hard

Fill all three blanks to complete the function returning the correct result.

DSA Go

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, [1])
    dp[0] = true
    for _, num := range nums {
        for j := [2]; j >= num; j-- {
            dp[j] = dp[j] || dp[j [3] num]
        }
    }
    return dp[target]
}

Drag options to blanks, or click blank then click option'

Atarget + 1

Btarget

C-

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Incorrect dp slice size causing index errors.

Looping forward instead of backward.

Using addition instead of subtraction inside dp index.

The dp slice size is target+1, loop from target down to num, and update dp[j] using dp[j - num].

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